HackerEarth Maximum Sum problem solution

YASH PAL, 31 July 202414 February 2026

In this HackerEarth Maximum Sum problem solution, we have given an array A of N integers. Now, you have to output the sum of unique values of the maximum subarray sum of all the possible subarrays of the given array A.

HackerEarth Maximum Sum problem solution

HackerEarth Maximum Sum problem solution.

#include <bits/stdc++.h>

using namespace std;

const int N = 5E3 + 5;
long long a[N];
set<long long> st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++)
        cin >> a[i];
    long long msf, cur;
    for(int i = 0; i < n; i ++) {
        for(int j = i; j < n; j ++) {
            if(j == i) {
                msf = a[j];
                cur = a[j];
                st.insert(a[j]);
            } else {
                cur = max(a[j], cur + a[j]);
                msf = max(msf, cur);
                st.insert(msf);
            }
        }
    }
    long long ans = 0;
    for(auto i : st)
        ans += i;
    cout << ans;
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
LL dp[50001];
set<LL> s;
int a[5001];
int main()
    {
        ios_base::sync_with_stdio(0);
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        for(int i = 1; i <= n; i++){
            LL mx = -1000000000;
            for(int j = i; j <= n; j++){
                if(dp[j - 1] < 0){
                    dp[j] = a[j];
                }
                else{
                    dp[j] = dp[j - 1] + a[j];
                }
                mx = max(mx , dp[j]);
                s.insert(mx);
            }
            for(int j = i; j <= n; j++){
                dp[j] = 0;
            }
        }
        LL ans = 0;
        for(LL i: s){
            ans += i;
        }
        cout << ans;
    }

coding problems solutions HackerEarth HackerEarth

Leave a Reply