# Hackerrank dp question !

can anyone explain me why my reccurence relation is wrong ??
question : Sherlock and Cost | HackerRank
my code : https://www.hackerrank.com/challenges/sherlock-and-cost/submissions/code/67767333
I have not memoized it ! Im getting wrong answer for some test cases !

since a[i]>=1 you already know what max and min will return. no need to make 120+ char line code.
What does the return value of f(i, sum) represents?
Also why do you use long long for everything?

My code:

``````#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
int dp[N][2]; // dp[i][j] => max cost of a[1..i] with a[i] = jth element of {1, b[i]}

int cost(vector <int> b) {
int n = b.size();
for(int i=1;i<n;i++) {
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + abs(1-b[i-1]));
dp[i][1] = max(dp[i-1][0] + abs(b[i]-1), dp[i-1][1] + abs(b[i]-b[i-1]));
}
return max(dp[n-1][0], dp[n-1][1]);
}

int main() {
int t;
cin >> t;
for(int a0 = 0; a0 < t; a0++){
int n;
cin >> n;
vector<int> arr(n);
for(int arr_i = 0; arr_i < n; arr_i++){
cin >> arr[arr_i];
}
int result = cost(arr);
cout << result << endl;
}
return 0;
}``````

I dont see any WA,they are tle’s.And yeah ur code is not visible.

yeah they are TLE’s but when i check for some cases im getting slight variation in my answer !
ideone : U3jKFb - Online C++0x Compiler & Debugging Tool - Ideone.com

anyone pls help me !

Thank you for ur help bro !
But can you explain me where Im going wrong ? Iam checking all four possiblities i.e,(min,min),(min,max),(max,min),(max,max) for current and next element and picking up the maximum sum among them !

ok so you are using sum as an accumulator then?

Here is why your approach is wrong: you set the value of (a[i], a[i+1]) so as to maximize the answer greedily then you again modify the value of (a[i+1], a[i+2]). So basically you may use 2 values at the same time for a[i+1]

oh got it !
Thanks bro !