4
$\begingroup$

Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.

Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.

Example input: (2, -1, -2, 1, -4, 2, 8)

Example output: ((1, 4), (5, 6))

The output above is the indices of these two subarrays: ((-1, -2, 1, -4,), (2, 8))

I've been trying to reduce this problem to the Maximum subarray problem but with no success.

$\endgroup$
  • $\begingroup$ Hint, two contiguous subarrays means the last element of the first subarray is adjacent to the first element of the second subarray. Did you see a parameter here? $\endgroup$ – John L. Apr 11 at 17:35
  • $\begingroup$ I believe OP did not mean that the two subarrays are adjacent. My guess is that they used the word 'contiguous' to just mean that the two disjoint subarrays are independently contiguous themselves, which I think is redundant given the definition of subarray. But it is still used in many places. eg. "finding a contiguous subarray with the largest sum" in en.wikipedia.org/wiki/Maximum_subarray_problem $\endgroup$ – CodeChef Apr 11 at 17:45
  • 1
    $\begingroup$ @CodeChef Unfortunately, the example given in the question can be considered the supposed interpretation of "contiguous subarray.", although it does not rule out the possibility to treat is as "redundant" as well. Treating it as meaningful and not redundant shows, I believe, the most respect to the almost universal convention that "subarray means contiguous elements" and, hence, the the author of the original problem. $\endgroup$ – John L. Apr 11 at 17:53
  • 1
    $\begingroup$ Yes, I agree. My guess was also based on having seen this problem (the variant I assumed it to mean) multiple times in relation to interview questions, but you are absolutely right. $\endgroup$ – CodeChef Apr 11 at 17:57
2
$\begingroup$

Because the two subarrays are disjoint, there exists at least one index $m$ such that one entire subarray lies $\leq m$ and the other subarray lies $\gt m$.

But we do not know what this $m$ is, beforehand. So let us iterate over all the $n$ possibilities for $m$. Now if an $m$ is fixed, then the problem reduces to the Maximum subarray problem, and the Minimum subarray problem. This is because for the absolute difference to be the largest, one side of $m$ should have the maximum possible subarray, and the other side should have the minimum possible subarray. So we try both of these options and take the maximum absolute difference among the two.

But this is still $\mathcal{O}(n^2)$, because there are $n$ different values of $m$, and for each of those values, we have to spend $\mathcal{O}(n)$ time to compute the needed minimum and maximum subarrays.

The next observation is to note that a single $\mathcal{O}(n)$ run of the Maximum subarray algorithm on the entire array can actually give us one of the needed values for all values of $m$:

Given: int A[n]

MaxSubarrayTill[0] = A[0]
MaxSubarrayEndingAt[0] = A[0]
for(i = 1; i < n ; i++)
{
    MaxSubarrayEndingAt[i] = max{A[i], MaxSubarrayEndingAt[i - 1] + A[i]}
    MaxSubarrayTill[i] = max{MaxSubarrayTill[i - 1], MaxSubarrayEndingAt[i]}
}

Here, $\text{MaxSubarrayTill}[i]$ denotes the maximum sum subarray which ends $\le i$, and $\text{MaxSubarrayEndingAt}[i]$ denotes the maximum sum subarray which ends at index $i$.

Similarly, we can compute the $\text{MinSubarrayTill}[i]$ array in $\mathcal{O}(n)$ time. And by repeating the same two algorithms in reverse (ie. from the end of the array to the beginning), we can get $\text{MaxSubarrayFrom}[i]$ and $\text{MinSubarrayFrom}[i]$.

So in $\mathcal{O}(n)$ time we have precomputed all the values that we needed in the first algorithm, which we can now go back to. Interate over all the values of $m$, and find the largest absolute difference in $\mathcal{O}(n)$ time.

If the problem also stipulates that the two subarrays should be adjacent, then we can leave out $\text{MaxSubarrayTill}[i]$ and its analogous arrays, and instead only consider $\text{MaxSubarrayEndingAt}[i]$ and its analogous three other arrays. The rest of the algorthm remains the same.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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