HackerEarth Maximum Sum problem solution

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.

Topics we are covering

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