I'm 13 years old and learning dynamic programming to improve my problem-solving abilities. Could someone please help me solve this problem? It has a dp kinda vibe, I learned how to memoize it, but I feel like I am not able to write the transition function, or the recursion statement in this properly. Can someone help me with my approach I have some mistake still Link: https://codeforces.me/contest/1343/problem/C
void solve(vector<ll>&a,ll idx,ll &maxSum,ll &sum,ll flag)
{
if(idx == a.size()){
maxSum = max(maxSum,sum);
return ;
}
if(a[idx] < 0 && flag == 1)
{
sum += a[idx];
solve(a,idx+1,maxSum,sum,0);
sum -= a[idx];
solve(a,idx+1,maxSum,sum,1);
}
else if(a[idx] > 0 && flag == 0)
{
sum += a[idx];
solve(a,idx+1,maxSum,sum,1);
sum -= a[idx];
solve(a,idx+1,maxSum,sum,0);
}
}
void solve(){
ll n;
cin >> n;
vt<ll> a(n);
cin >> a;
ll sum = 0,maxSum = -1e9;
solve(a,0,maxSum,sum,0);
solve(a,0,maxSum,sum,1);
cout << maxSum << endl;
}