Maximize sum of absolute difference | Codenation Hiring Challenge

general
,
1

Given an array “A” of size of n. You can choose any subarray and reverse it at most once. Find maximum possible sum of absolute difference of consecutive elements, i.e., abs(A[1]-A[2])+abs(A[2]-A[3])+…+abs(A[n-1]-A[n]). Can anyone help me in this problem ?
Constraints: 1<=n<=100000

2 Likes
2

Codenation was probably just playing with our feelings xD

3

Take a array of dp[4][n] store -ve of abs(a[i] - a[i-1]) in all dp[0],dp[1],dp[2],dp[3].
there will be only 4 possibilities
let the reversed indexes be x and y
thus we will be adding abs(a[y] - a[x]) - (i) and abs(a[y+1] - a[x+1]) - (ii)

So 4 possibilities are for a index i will be a[y] - a[x] + a[y+1] - a[x+1] , a[x] - a[y] + a[y+1] - a[x+1] , a[x] - a[y] + a[x+1] - a[y+1] , a[y] - a[x] - a[y+1] + a[x+1] - (iv)…

dp[j][i] += a[i] - a[i-1]

If we see 4 possibilities of abs value of (i) and (ii). So at dp[0][i] we can store a[i] + a[i+1], dp[1][i] = a[i+1] - a[i], dp[2][i] = -a[i] - a[i+1], dp[3][i] = a[i] - a[i+1] …

dp[0][i] += a[i] + a[i+1];
dp[1][i] += a[i+1] - a[i];
dp[2][i] += -a[i+1] - a[i];
dp[3][i] += a[i] - a[i+1];

From (iv) we can see that if we are at index i with dp[0][i] we need to find maximum value possible from dp[2][i] and if we are using value of dp[1][i] we need to find previous maximum possible using dp[3][i] to get the above 4 different possibilities the max value will be given by maximum sum.
And all other segments of array will add abs(a[i] - a[i-1]) to solution.

So we can find the solution in O(n)… :slight_smile:
A question which uses similar logic Problem - E - Codeforces.

1 Like
4

It can be solved by simply making 4 cases and calculating the maximum answer of the 4 cases:

Let value(i) = |a[i] - a[i - 1]|

We need to maximize (|a[r] - a[l - 1]| + |a[r + 1] - a[l]| - value(l) - value(r + 1)) …(1)

(1) can be written as:

max(max(a[r] - a[l - 1], a[l - 1] - a[r]) + max(a[r + 1] - a[l], a[l] - a[r + 1]) - value(l) - value(r + 1))

Now we have 4 possible options here,

one of them is

max(a[r] - a[l - 1] + a[r + 1] - a[l] - value(l) - value(r + 1))
= max(a[r] + a[r + 1] - value(r + 1) - a[l - 1] - a[l] - value(l))

Now as its easy to see that r and l have been separated and we can calculate separately for l and r in O(n).

Then we can iterate on r and maintain the best index or location for l.

1 Like
5

It feels bad when you can’t even get first problem.

6

Problem statement

1 Like