[toph.co] Subarray Sum

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Subarray Sum
Source            : toph.co
Category          : Dynamic Programing
Algorithm         : Non Classical
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
 
static const int MAXN = 5000 + 55;
 
typedef long long ll;
 
int n, N, K;
ll arr[MAXN], cumarr[MAXN];
ll dp[MAXN][MAXN];
bool vis[MAXN][MAXN];
 
ll solve(int nn, int kk)
{
    if (nn > N || kk < 0) return 0;
    ll &ret = dp[nn][kk];
    bool &v = vis[nn][kk]; 
    if (v) return ret;
    v = 1;
    ll choice1 = -1e17;
    ll choice2 = -1e17;
    ll choice = cumarr[nn];
    if (cumarr[nn] < 0 && kk > 0)
    {
        choice1 = cumarr[nn] + solve(nn+1, kk);
        choice2 = solve(nn+1, kk-1);
        choice = max(choice, max(choice1, choice2));
    }
    else
    {
        choice = max(choice, cumarr[nn] + solve(nn+1, kk));
    }
 
    return ret = choice;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++)
    {
        cin >> n >> K;
        ll maxi = -1e17;
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
            if (arr[i] > maxi) maxi = arr[i];
        }
        cout << "Case " << tcase << ": ";
        int id = -1;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] < 0)
            {
                if (sum > 0)
                {
                    id++;
                    cumarr[id] = sum;
                    sum = 0;
                }
                id++;
                cumarr[id] = arr[i];
            }
            else
            {
                sum += arr[i];
            }
        }
        if (sum > 0)
        {
            id++;
            cumarr[id] = sum;
        }
        N = id;
        memset(vis, 0, sizeof vis);
        ll ans = maxi;
        for (int i = 0; i <= N; i++)
        {
            ll ss =  solve(i, K);
            ans = max(ans, ss);
        }
        cout << ans << endl;
    }
}