Join Us
Loading Similar Posts
Entering edit mode
1. Subarray Sum
ll solve(vector<int> &arr){
int n=arr.size();
vector<ll> pf(n),sf(n);
pf[0]=arr[0];
sf[n-1]=arr[n-1];
for(int i=1;i<n;i++) pf[i]=arr[i]+pf[i-1];
for(int i=n-2;i>=0;i--) sf[i]=arr[i]+sf[i+1];
ll sm=0,mn=0;
ll mx=-1e18;
for(int i=0;i<n;i++){
sm+=arr[i];
if(sm>0) sm=0;
mn=min(mn,sm);
mx=max(mx,pf[i]-2*mn-(i<n-1?sf[i+1]:0));
}
return mx;
}
Entering edit mode
Subarray SUM using DP
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int arr[200005];
int dp[200005][5];
int rec(int i, int which)
{
if (i >= n)
{
return 0;
}
if (dp[i][which] != -1)
return dp[i][which];
if (which > 4)
{
return -1e17;
}
int ans = 0;
if (which == 1)
{
int opt1 = arr[i] + rec(i + 1, 1);
int opt2 = rec(i, 2);
ans = max(opt1, opt2);
}
else if (which == 2)
{
int opt1 = -arr[i] + rec(i + 1, 2);
int opt2 = rec(i, 3);
ans = max(opt1, opt2);
}
else if (which == 3)
{
int opt1 = arr[i] + rec(i + 1, 3);
int opt2 = rec(i, 4);
ans = max(opt1, opt2);
}
else
{
int opt1 = -arr[i] + rec(i + 1, 4);
ans = opt1;
}
return dp[i][which] = ans;
}
int32_t main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr[i];
memset(dp, -1, sizeof(dp));
cout << rec(0, 1);
return 0;
}
