0
$\begingroup$

I have stumbled upon this problem online:

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... > A(j) for which the sum of elements in the subsequence is maximized.

Now my solution is so: I assume that the sequence is stored in an array. We need 2 arrays under the original array, one is a flag array A and the other is a real number array B.

Take the first element as the subsequence we are searching for, put a 1 under it in A, and put the value of the element in it's index in B (which is right under it's index in A). Go to the next element. If it isn't negative, put a 1 under it in A, and put the sum of that element and the element before him in B. If it's negative, put a 0 under it in A, and go to the next element, starting a new subsequence.

The complexity is O(n) time because I run on the whole sequence once.

Example:

Sequence: 4 33 -24 3 4 2 -5 6 19 -11 32 40 -30 5 6
Array A: 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1
Array B: 4 37 13 3 7 9 4 6 19 8 32 70 40 5 11

My question is: is that the wanted solution? and does it really run in O(n) time?

$\endgroup$

closed as unclear what you're asking by D.W., Luke Mathieson, David Richerby, Wandering Logic, Juho May 26 '14 at 13:39

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ There is no such thing as the intended solution, and if there is, we have no way of knowing it. There are only correct solutions and wrong solutions. You indicate that you're not sure whether your solution is correct. I suggest you try harder convincing yourself that your solution is correct. $\endgroup$ – Yuval Filmus May 15 '14 at 14:41
  • $\begingroup$ You don't even specify what your algorithm will return. So this can't be a correct solution. $\endgroup$ – FrankW May 15 '14 at 15:36
  • $\begingroup$ @Yuval Filmus are you hinting that my solution is correct? $\endgroup$ – HaloKiller May 15 '14 at 15:43
  • $\begingroup$ @FrankW let's say we return the sequence itself $\endgroup$ – HaloKiller May 15 '14 at 15:44
  • $\begingroup$ @Trinarics That is not a valid solution, unless it happens to be ordered. $\endgroup$ – FrankW May 15 '14 at 15:49
3
$\begingroup$

Your algorithm does not yield the solution. An extension of your algorithm that follows will provide a solution. You need to mark the extremes of consecutive 1's in the flag array (an obvious observation ). For example, the flag array is 1111101111 then you need to mark 0,5,9 indices (zero based) and for every pair of extremes you need to find the difference computed in prefix sum array. The number of marker indices are of the order of n. So number of pairs are of the order n^2.

$\endgroup$
0
$\begingroup$

Here is another suggestion. Given the original array $A_1,\ldots,A_n$, define a new array $B_0, B_1,\ldots,B_n$ by $$B_i = \sum_{j=1}^i A_j. $$ This is useful since $$\sum_{j=i_1}^{i_2} A_j = B_{i_2} - B_{i_1-1}. $$ So now we want to find the maximum value of $B_{i_2} - B_{i_1-1}$. The idea is to scan the array from left to right, keeping track of the optimal choice of $i_1$ at any given moment. I will let you fill in the details.

$\endgroup$
  • $\begingroup$ By the way, I believe that the full algorithm appears in some other answer on this site. It's apparently a favorite homework problem. $\endgroup$ – Yuval Filmus May 15 '14 at 18:39
  • $\begingroup$ when you said I should convince myself that my solution is correct, you meant that it is correct? $\endgroup$ – HaloKiller May 15 '14 at 19:05
  • 2
    $\begingroup$ @Trinarics I didn't read your solution. All I meant was that the way to know whether your solution is correct is to get convinced that it is correct, i.e., to prove its correctness. You run into trouble if you can't prove it, since you don't know whether the proof is just difficult, or your algorithm actually doesn't work. In that case I would suggest trying it out on a few examples, perhaps even programming it and trying it on random examples. $\endgroup$ – Yuval Filmus May 15 '14 at 19:59

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