3
$\begingroup$

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 106.
  • Array values can be between -109 to 109.

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?

$\endgroup$
4
  • 1
    $\begingroup$ So the span of a subsequence $X = x_i, x_i+1, \dots, x_{i'}$ is $\text{span}(X) = \max(X) - \min(X)$ and you want to maximize the sum of the spans? $\endgroup$
    – Pål GD
    Mar 6, 2021 at 15:21
  • $\begingroup$ @PålGD I want to maximize the sum after making such span splits optimally. Span length could be small or big, doesn't matter. Yes(after you edited). $\endgroup$
    – nice_dev
    Mar 6, 2021 at 15:23
  • 1
    $\begingroup$ Would-be employers might be looking for skills promising revenue. Like asking in the right place. $\endgroup$
    – greybeard
    Mar 6, 2021 at 16:07
  • $\begingroup$ @greybeard Actually this hiring challenge was like an online contest. Pretty unlikely that the employer would do such a thing as the system gives a time out error message for large cases but gave correct answer for smaller ones. However, you never know ;) $\endgroup$
    – nice_dev
    Mar 6, 2021 at 16:30

2 Answers 2

4
$\begingroup$

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];
    }
$\endgroup$
2
  • 1
    $\begingroup$ It should run well within 0.1 second when $n= 10^6$. $\endgroup$
    – John L.
    Mar 7, 2021 at 1:17
  • $\begingroup$ Apologies for the late reply. Thank you so much for such a comprehensive explanation. Still trying to grasp the entire logic. Yes, it runs perfectly under 0.1 - 0.2 seconds for n = 10^6. I will ping if still anything is unclear, but I get what you mean when you say weakly increasing or weakly decreasing. $\endgroup$
    – nice_dev
    Mar 8, 2021 at 5:26
5
$\begingroup$

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$.)

$\endgroup$
6
  • $\begingroup$ "if one subarray is monotone increasing, then the following subarray is monotone decreasing." Consider $[1,4,2,3]$. Both $[1,4]$ and $[2,3]$ are increasing. $\endgroup$
    – John L.
    Mar 7, 2021 at 0:46
  • $\begingroup$ Right, more accurately, you shouldn’t break a monotone sequence. $\endgroup$ Mar 7, 2021 at 6:37
  • $\begingroup$ "no monotone subarray is 'broken'". Is monotone subarray "[7,6,5]" broken if we split [2,7,6,5] into [2,7] and [6,5]? $\endgroup$
    – John L.
    Mar 7, 2021 at 6:50
  • $\begingroup$ No, since if you join them, you don’t get a monotone subarray. $\endgroup$ Mar 7, 2021 at 6:53
  • 1
    $\begingroup$ A sequence is monotone if it is nonincreasing or nondecreasing. $\endgroup$ Mar 8, 2021 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.