1
$\begingroup$

I've been stuck on this problem for some time, and I don't want to just look at an answer. I'd like a hint(s) so that I can get myself thinking in the right direction so that I might gain more insight into solving similar types of algorithm problems. This exercise is actually from CLRS on the section on Divide-and-Conquer algorithms, soon after it introduced what recursion is.

I figured out the pseudocode for (easier) then coded up an n^2-time solution (though I thought it should be n(n-1)/2-time since I thought there were exactly n Choose 2 possible subarrays, but I guess that's a different issue), and I understand the provided O(nlogn) recursive solution.

Here's the problem-statement from CLRS 4.1-5:

Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j], extend the answer to find a maximum subarray ending at index j+1 by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1], for some 1 <= i <= j+1. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index j.

Also, of course, the input is A[1..n].

Ok, so I think I understand why the hint makes sense by supposing not then choosing a counter-example (i.e., the following array: [-|+|+|-|neg_1|anything|neg_2|anything|anything] where A[-] represents some non-positive number and A[+] represents some positive number, and A[neg_1] and A[neg_2] are negative; suppose A[neg_1+1..neg_1+1] is a current maximum subarray up till that index, then we find that |A[neg_2]| > A[1..neg_1+1], but A[neg_2+1] > |A[neg_2]| so then the current maximum subarray is A[1..neg_2+1] up till that index. This example shows why the hint makes sense, and it also finds a fault in my attempted O(n)-time solution):

Inside a loop from 1 to n:

  • we call the maximum-sum interval "interval"
  • we call the soonest negative number after the max-sum interval "neg"
  • If sum_from_neg > neg, take {interval[1], j+1} as "interval"
  • Otherwise, if sum_from_neg > max_sum take that interval (A[neg+1..j+1]).

This idea doesn't quite work, as I tried to illustrate with my example array from above.

Edit: @ryan's comment (the first comment to this post) didn't really help me much. Anybody have other hints?

$\endgroup$
  • $\begingroup$ I don't think the focus should be so much on individual negative numbers. Imagine we have the sum of max subarray $A[i \dots j]$. Now we observe $A[j+1]$. There's 2 things that could happen, the sum increases or decreases. Increase is good, although decrease may not be bad in the end so we're not sure. After adding $A[j+1]$ you should really consider whether the sum becomes negative or positive. If the sum becomes negative, what will happen when considering the next value? Think about this, it may help you get to the next solution in constant time. $\endgroup$ – ryan Jun 24 '17 at 2:36
  • $\begingroup$ Sorry, that doesn't really help me. Do you have another hint? $\endgroup$ – user3773048 Jun 27 '17 at 23:45
  • $\begingroup$ If the sum becomes negative, then I need to have a sum not counting that number that is greater than the current sum of the max subarray, which I could use for the time being, but then if that sum is greater than that negative number, I would combine the two intervals and use that even larger sum and even larger interval... If the sum is positive, simply take the larger interval between the one corresponding to the sum and the max-interval sum? This seems greedy to me etc.... I'm not really seeing the solution this way... $\endgroup$ – user3773048 Jun 27 '17 at 23:51
  • $\begingroup$ The solution $f(j+1)$ for the subproblem on $A[1 \dots j+1]$ can be found as the better of two things: the maximum-sum subarray of $A[1 \dots j]$ (which we already computed; it's $f(j)$, the solution for the subproblem on $A[1 \dots j]$), and the maximum-sum subarray ending at $A[j+1]$. The trick is to compute this second quantity quickly. Hint: Suppose we also compute the maximum-sum subarray ending at each position $j$; call this $g(j)$. If we know both $f(j)$ and $g(j)$, can we compute both $f(j+1)$ and $g(j+1)$ quickly? $\endgroup$ – j_random_hacker Jul 2 '17 at 12:23

Your Answer

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

Browse other questions tagged or ask your own question.