Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one

Question

I was asked this in a hiring challenge that I gave today on HackerEarth:

Question/Problem statement:

Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum of difference between maximum and minimum in each of those subarrays.

Examples:

[1, 2 , 1 , 0, 5]

You can split them into 3 subarrays [1,2] , [1], [0,5].

Through this split, you can obtain maximum sum like (2-1) + (1-1) + (5-0) = 6.

Another example:

[1,4,2,3]

You can split them into 2 subarrays [1,4] , [2,3].

Through this split, you can obtain maximum sum like (4-1) + (3-2) = 4

Constraints:

• Array length can be up to 10⁶.
• Array values can be between -10⁹ to 10⁹.

My attempt:

I made a brute force DP attempt which was partially accepted. Below is the approach.

long[] dp = new long[N + 1];
 
for(int i = N-1;i >= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j < N; ++j){
        min = Math.min(min, A[j]);
        max = Math.max(max, A[j]);
        dp[i] = Math.max(dp[i],max - min + dp[j + 1]);
    }
}
 
print(dp[0])

Issue:

Can anyone share with me how this can be solved efficiently?

Answer 1

Yuval's answer explains the initial intuition and analysis. Here is a detailed explanation and an efficient algorithm in Java.

Given a (sub)array $B$, let $\min(B)$ and $\max(B$) be its minimum element and maximum element respectively. $B$'s range is the interval $[\min(B), \max(B)]$. Let the difference of $B$ be $d(B)=\max(B)-\min(B)$.

Given $p$ that is a partition of the given array into subarrays, let $sd(p)$ be the sum of differences of those subarrays.

---

Splitting Lemma. Given partition $p$, two contiguous elements $n_1$ and $n_2$ in some (sub)array $B$ of $p$, let us split $B$ between $n_1$ and $n_2$ into subarrays $B_1$ and $B_2$, obtaining a new partition, which will be called $p'$. If both $n_1$ and $n_2$ are in $B_1$'s range or both are in $B_2$'s range, then $sd(p) \le sd(p')$.

Here is how to understand the lemma.

• Subarrays in $p$ other than $B$ are not changed; so their contribution to the sum of differences will not decrease.
• When $B$ is split into $B_1$ and $B_2$, the only part of the range of $B$ that might get "missing" is the interval $[\min(n_1, n_2), \max(n_1, n_2)]$. If that interval is covered by either $B_1$ or $B_2$, the sum of differences will not miss that range.

---

Let $p$ be some partition of the given array.

• Suppose there is a peak in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a<b$ and $b>c$.

  • Suppose $a \le c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
  • Otherwise $a \gt c$. Symmetrically to the above, we will cut between $b$ and $a$.

• Suppose there is a valley in one of subarrays in $p$, i.e., three contiguous number $a,b,c$ such that $a>b$ and $b<c$.

  • Suppose $a \ge c$. We can split this subarray further into two subarrays by cutting between $b$ and $c$, arriving at partition $p'$. Since both $b$ and $c$ are in the range of the new subarray that contains $a$, $sd(p) \le sd(p')$.
  • Otherwise $a \lt c$. Symmetrically to the above, we will cut between $b$ and $a$.

---

The above shows that whenever a partition contains either a peak or valley in one of its subarrays, we can split that subarray to get a partition that is no less optimal.

In particular, cutting subarrays repeatedly if necessary, we can replace an optimal partition with another one that has no peak or valley in any of its subarrays.

Hence, in order to final the maximum sum, we only need to consider the partitions that has no peak nor valleys in all of its subarrays, i.e, each subarray is (weakly) increasing or (weakly) decreasing.

If two consecutive subarrays are, if considered together, is an increasing array or a decreasing array still, combining these two subarrays into one subarray will not decrease $sd$. So, we only need to consider subarrays each of whose endpoints is the endpoint of a maximal increasing run or a maximal decreasing run or its immediate neighbors.

---

Here is an implementation in Java that runs in $O(n)$ time. It should finish within half of a second when $n=10^6$.

    static long maximumSum_simplified(int[] A) {
        int len = A.length;

        // maxSum[i+1] will be the max sum out of A[0..i] for selected `i`s.
        long[] maxSum = new long[len + 1];
        // maxSum[0] = 0;  by Java default.

        // A[start..end] will be a maximal increasing run or a maximal decreasing run.
        for (int start = 0, end; start < len - 1; start = end) {
            end = start + 1;
            if (A[end] <= A[start]) {
                while (end + 1 < len && A[end + 1] <= A[end]) end++;
                for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
                    maxSum[i + 1] = Math.max(maxSum[start] + A[start] - A[i],
                            maxSum[start + 1] + A[start + 1] - A[i]);
                }
            } else {
                while (end + 1 < len && A[end + 1] >= A[end]) end++;
                for (int i = Math.max(end - 1, start + 1); i <= end; i++) {
                    maxSum[i + 1] = Math.max(maxSum[start] + A[i] - A[start],
                            maxSum[start + 1] + A[i] - A[start + 1]);
                }
            }
        }

        return maxSum[len];
    }

Answer 2

Some case analysis shows that:

• Without loss of generality, every subarray is monotone.
• Without loss of generality, no monotone subarray is "broken", that is, joining two adjacent subarrays cannot result in a monotone subarray.

This reduces the number of options in dynamic programming to $O(1)$, and so should lead to an $O(n)$ algorithm.

(It seems that some case analysis is still needed. For example, if the array is $a,b,c$, where $a<b>c$, then the best solution depends on whether $a<c$ or $a>c$.)