While submitting the test case 3 the test case is failing but while testing the test case 3 it is passing.
The code -
typedef long long ll;
ll dp[101][101][2];
ll solve2(ll *arr, ll n, ll k ,ll pos, ll trans , ll prevState) {
if(n < 0 || trans == k) {
return 0;
}
if (dp[pos][trans][prevState] != -1) {
return dp[pos][trans][prevState];
}
ll ans = solve2(arr,n-1,k,pos+1,trans,prevState);
if(prevState == 1) {
ans = max(ans, solve2(arr, n-1, k, pos+1, trans+1, 0) + arr[pos]);
} else {
ans = max(ans, solve2(arr,n-1,k,pos+1,trans,1) - arr[pos]);
}
return dp[pos][trans][prevState] = ans;
}
int main() {
ll t;
cin>>t;
while(t–) {
memset(dp,-1,sizeof(dp));
ll k, n;
cin>>k;
cin>>n;
ll *arr = new ll[n];
for(ll i = 0 ; i < n ; i++) {
cin>>arr[i];
}
cout << solve2(arr,n,k,0,0,0) << endl;
}
return 0;
}