Maximum Contiguous Subsequence Sum with longest sequence?

Question

I know how to find a maximum, contiguous, subsequence sum; but sometimes there's more than one subsequence with maximum sum. So, I need to find the index of those longest subsequences with the maximum sum. The only thing I thought of is brute force. What better options are there?

Here's a code I found on rosettacode which had the exact idea for my problem (but, sadly, the only programming language I know is Java), but it is writen in REXX:

/*───────────────────────────────────────────────────────────────*/
arg @                                  
say 'words='words(@) 'list='@          
say
sum=word(@,1)                          
w=words(@)                             
at=1                                   
L=0       

do j=1 for w;  f=word(@,j)

    do k=j to w; s=f

          do m=j+1 to k
          s=s+word(@,m)
          end   /*m*/

    _=k-j+1
    if (s==sum & _>L) | s>sum then do; sum=s; at=j; L=_; end
    end         /*k*/

end               /*j*/


seq=subword(@,at,L)
if seq=='' then seq="[NULL]"
sum=word(sum 0,1)
say 'sum='sum/1 "sequence="seq
/*───────────────────────────────────────────────────────────────*/

Results:

input 1 2 3 4 -777 1 2 3 4 0 0 
output
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0

sum=10 sequence=1 2 3 4 0 0

That's not a question. It's a problem description. And probably homework. sigh — mellamokb
– mellamokb, Commented Feb 28, 2011 at 21:25
I +1'd you for your ascii-art Owl face (it looks like an owl anyway.) I'm curious why 1 2 3 4 0 0 is a contiguous subsequence. Could you define contiguous subsequence for us? — corsiKa
– corsiKa, Commented Feb 28, 2011 at 21:26
@glowcoder: Isn't 1 2 3 4 0 0 found consecutively within the list? That would make it a contiguous subsequence. What's confusing about it? — mellamokb
– mellamokb, Commented Feb 28, 2011 at 21:28
@mellamokb What's confusing is why -777 1 2 3 4 0 0 isn't picked, since it's in list. What defines contiguous in this sense? — corsiKa
– corsiKa, Commented Feb 28, 2011 at 21:29
@glowcoder: Because the sum would be smaller...? We want the largest contiguous subsequence that also has the maximum value. That would reduce the sum from 10 to -767, so it's not a candidate. — mellamokb
– mellamokb, Commented Feb 28, 2011 at 21:33

Wang · Accepted Answer · 2011-02-28 21:29:22Z

2

If this is homework, I'd recommend you take a look at dynamic programming algorithms. In particular, you can simplify one of the steps of the Smith-Waterman local string alignment to do exactly what's needed here. The key is to read up on the idea of optimal substructure and ask yourself, is there some kind of subproblem involved which I can solve using only local information at each point in the sequence?

answered Feb 28, 2011 at 21:29

Wang

3,3531 gold badge27 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

bot Over a year ago

I'm not asking for my homework, just a help to learn,, especially the ideas behind the source code i'd given above..or anylinks (due hardly acsess academic literature )so i could learn more 'bout this problem.. it's called contiguous subseq. cuz its connected consecutively within the sequence.,,that's how i explained it,,since u've found that english isnt my native language,,^_",, 1 2 3 4 0 0 had the max sum than any subseq,,and had longer than just 1 2 3 4 or 1 2 3 4 0,,

Collectives™ on Stack Overflow

Maximum Contiguous Subsequence Sum with longest sequence?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related