tusharjape007's blog

I need an approach to solve this question.
By tusharjape007, history, 5 years ago, In English

I recently encountered a question on a contest organised by CodeNation which is as follows.

You have been give an array comprising of numbers (ranging from -10^9 to +10^9) and the value of an array is defined as the sum of the absolute differences between each pair of consecutive entries in the array. You are allowed to reverse a contiguous subarray of the given array. What would be the maximum possible value of the array if you apply the given operation utmost once?

I am stuck on the O(n^2) approach to this problem. Can anyone please help me out?

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

There are two corner cases when the reversing subarray contains the first array element and when it contains last array element. We can consider those cases separately. Also if the array size is small (say n <= 3) the answer can be easily calculated.

Suppose we reverse the subarray [b...c] in the initial array m = [... a b ... c d ...]. So the difference in the array value will be

|a - c| + |d - b| - |a - b| - |c - d|

This value can be positive only when both a, b are greater than any of c, d or both c, d are greater then a, b. If we have first case then the difference can be expressed as

2 * (min(a, b) - max(c, d))

We can support two additional arrays for the adjacent numbers: minp[n] and rmaxp[n]. minp[i] represents the minimum value of the pair values m[i] and m[i+1], keeping the maximum value among all values from the beggining of the initial array:

minp[0] = min( m[0], m[1]);
for( i = 1; i < n-1; ++i)
{
  minp[i] = min( m[i], m[i+1]);
  if( minp[i] < minp[i-1] ) minp[i] = minp[i-1];
}

rmaxp[i] means the maximum value of m[i] and m[i+1], keeping the minimum value among all values from the end of the initial array:

rmaxp[n-2] = max( m[n-2], m[n-1]);
for( i = n-3; i >= 0; --i)
{
  rmaxp[i] = max( m[i], m[i+1]);
  if( rmaxp[i] > rmaxp[i+1] ) rmaxp[i] = rmaxp[i+1];
}

Now all we should do is to find maximum positive value of minp[i-1]-rmaxp[i+1] for each valid index i (because the index of number b should be strictly smaller than the index of number c). The second case can be proceeded analogously.

PS Couldn't you give the link to the problem?

→ Reply