Hackerrank dp question !

general
1

can anyone explain me why my reccurence relation is wrong ??
question : https://www.hackerrank.com/challenges/sherlock-and-cost/problem
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 !

2

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

3

yeah they are TLE’s but when i check for some cases im getting slight variation in my answer !
ideone : https://ideone.com/U3jKFb

4

anyone pls help me !

5

Your code is not readable in current state. Please format it better.
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;
}
6

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 !

7

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]

8

oh got it !
Thanks bro !