Any help will be appreciated for Question below

general
1
2
Hint 1

Can you prove there always exists an optimal solution with A_i=1 or A_i=B_i?

Hint 2

Imagine a cartesian plane with the points (i, B_i). Make a line that may change direction at x=i. The score of the line is just the y distance moved. When the line does not pass through (i,B_i) or (i,1), can you see that there also exists a solution with equal or more value where it does pass through (i,B_i) or (i,1)?

3

As we have to maximize difference of consequetive elements then it is quite intutive that this difference is maximized only when in expression |A-B|:

  1. A is maximized and B is minimized. (B=1).
  2. B is maximized and A = 1

Using these two observations we can construct a dp solution.

  1. Let’s try to solve for an array B of size n.
  2. Using the above observations, for each B[i] we need to pick either 1 or B[i] because, picking any other value between (1, B[i]) cant maximize our function :slight_smile:
  3. Okay so we can now form a dp state like dp[n][type] . Here n is the index of the array and type indicates if the last chosen element at index n was Minimum(1) or maximum (B[n]). So we need Nx2 dp matrix.
dp[n][0]  -> When last chosen element was 1
dp[n][1] -> when last chosen element was B[n]
  1. Finally we can solve for n+1 as
// Choose 1 at current index i and check if maximum occurs with either 1 
// or B[i-1] at last i-1.
dp[i][0] = max(dp[i-1][0], abs(1-B[i-1]) + dp[i-1][1]);
// Choose B[i] now , and repeat the same.
dp[i][1] = max(abs(B[i]-1) + dp[i-1][0], abs(B[i]-B[i-1]) + dp[i-1][1]);
  1. My Solution :
int dp[100000][2];
// Complete the cost function below.
int cost(vector<int> B) {
    memset(dp, 0, sizeof(dp));
    int n = B.size();
    dp[0][0]=0;
    dp[0][1]=0;
    for(int i=1; i<n; i++) {
        dp[i][0] = max(dp[i-1][0], abs(1-B[i-1]) + dp[i-1][1]);
        dp[i][1] = max(abs(B[i]-1) + dp[i-1][0], abs(B[i]-B[i-1]) + dp[i-1][1]);
    }

    return max(dp[n-1][0], dp[n-1][1]);
}

Hope that helps :slight_smile:

4

There’re some cases where consecutive elements are 1’s and still, it maximizes the overall maximum.
How to explain that by intuition you stated above?
Consider this case,
B: 3 2 2 10
max occurs at 3 1 1 10 i.e sum = 11.

As we have to maximize difference of consecutive elements then it is quite intuitive that this >difference is maximized only when in expression |A-B|:

  1. A is maximized and B is minimized. (B=1).
  2. B is maximized and A = 1
5

Yes you are absolutely correct.

As we have to maximize difference of consecutive elements then it is quite intuitive that this >difference is maximized only when in expression |A-B|:

I mentioned these above lines to form the idea that selecting numbers between (1, B[i]) doesn’t make any sense as they cant cause maxima or minima.

Using the above observations, for each B[i] we need to pick either 1 or B[i] because, picking any other value between (1, B[i]) cant maximize our function :slight_smile:

So for each consecutive i and i+1 in B, we will try to maximize the difference but it maybe the case that maximizing (i-1, i ) and (i+1, i+2 ) gives us much higher value. So, the above-mentioned dp solution takes this into the account as well. Have a look here:

dp[i][0] = max(dp[i-1][0], abs(1-B[i-1]) + dp[i-1][1]);

We picked up 1 at i and checked if maximum occurs when last picked number was 1 or when it was B[i].
So while processing you array B: 3 2 2 10 at index 2

At i = 2
dp[2][0] = max(fun([3, 1, 1]) , fun([3 ,2 ,1]))
dp[2][1] = max(fun([3, 1, 2]) , fun([3 ,2 ,2]))

At i = 3
dp[3][0] = max(fun([3, 1, 1, 1]), fun([3, 1, 2, 1]))
dp[3][1] = max(fun([3, 1, 1, 10]), fun([3, 1, 2, 10]))

fun([x, y, z]) = |y-x | + |z - y|.

Feel free to ask if you still have any doubt. :slight_smile: