# Problem Link:

# Difficulty:

Simple

# Pre-requisites:

Dynamic Programming

# Problem:

Given an array D[1…N], find max(abs((D[i] + … + D[j]) - (D[k] + … D[l])) : 1<= i <= j < k <= l <= N).

# Explanation:

Let us look at the final solution, and work backwards. Let the final solution be due to some i0, j0, k0, l0. We now have two cases:

Case 1: D[k0] + … + D[l0] <= D[i0] + … + D[j0].

In this case, we get that among all possible choices of l, D[k0] + … + D[l] is MINIMUM for l = l0. Else, we could choose such l, and this would give us a larger absolute difference. We also get, that among all 1 <= i <= j <= k0-1, D[i] + … + D[j] is MAXIMUM.

Case 2: D[k0] + … + D[l0] > D[i0 + … + D[j0].

In this case, among all possible choices of l, we choose l0 to give the MAXIMUM value of the sum, and we choose i0, j0 to give the MINIMUM possible sum.

Hence, it would be useful precomputing values that answer “what is the [minimum|maximum] value I can get if I [start|end] at position i?”

### Solution 1

The above setting motivates the following few definitions:

HardLeftMin(i) = Minimum value of the sum of a contiguous subarray whose rightmost point = i.

HardLeftMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point = i.

SoftLeftMin(i) = Minimum value of the sum of a contiguous subarray whose rightmost point <= i.

SoftLeftMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point <= i.

HardRightMin(i) = Minimum value of the sum of a contiguous subarray whose leftmost point = i.

HardRightMax(i) = Maximum value of the sum of a contiguous subarray whose rightmost point = i.

Recurrences for the above are easy to find:

HardLeftMin(i) = min(D[i], D[i] + HardLeftMin(i-1)) : either you select position i-1 as well in your subarray and take the best from there, or you don’t even take position i-1.

HardLeftMax(i) = max(D[i], D[i] + HardLeftMax(i-1)) : similarly.

HardRightMin(i) = min(D[i], D[i] + HardRightMin(i+1)) : similarly.

HardRightMax(i) = max(D[i], D[i] + HardRightMax(i+1)) : similarly.

SoftLeftMin(i) = min(HardLeftMin(i), SoftLeftMin(i-1)) : either your minimum ends at points i, or it ends at some point <= i-1.

SoftLeftMax(i) = max(HardLeftMax(i), SoftLeftMax(i-1)) : similarly.

Note that, using the above recurrences, we can calculate all the arrays in O(N) time using dynamic programming.

Finally, our case (1) will be covered by SoftLeftMax(j0) - HardRightMin(j0+1), and case (2) will be covered by HardRightMax(j0+1) - SoftLeftMin(j0).

Iterate over all values of j0, and take the maximum, as your answer. This again takes O(N) time to run.

### Solution 2

This solution cleverly disposes of SoftLeftMin, SoftLeftMax() functions and works relying on the following claim.

Claim: Without loss of generality, k0 - j0 = 1. That is, we can consider our optimal phases as being consecutive.

Let us say that OPT returned i, j, k, l, with k-j > 1. Now, consider sum S = D[j+1] + D[j+2] + … + D[k-1]. If S >= 0, then it can be added to the larger of the two segments [i…j], [k…l]. If S <= 0, then the segment can be added to the smaller of the two segments [i…j], [k…l]. In both cases, it gives us a Delish value atleast as good as the Optimal. Hence, wlog, the two segments we choose are consecutive.

Thus, finally, we iterate over j, and consider abs(LeftMax(j) - RightMin(j+1)) and abs(RightMax(j+1) - LeftMin(j)) as candidates. This approach was used by the Setter.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here