Task

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.



An empty subsequence is considered to have the sum of   0;   thus if all elements are negative, the result must be the empty sequence.




 
'Greatest_subsequential_sum
 
N= 20   'number of elements
 
randomize 0.52
for K = 1 to 5
    a$ = using("##",int(rnd(1)*12)-5)
    for i=2 to N
        a$ = a$ +","+using("##",int(rnd(1)*12)-5)
    next
    call maxsumseq a$
next K
 
sub maxsumseq a$
    sum=0
    maxsum=0
    sumStart=1
    end1 =0
    start1 =1
 
    token$="*"
    i=0
    while 1
        i=i+1
        token$=word$(a$, i, ",")
        if token$ ="" then exit while    'end of stream
        x=val(token$)
        sum=sum+x
        if maxsum<sum then
             maxsum = sum
             start1 = sumStart
             end1 = i
        else
            if sum <0 then
                sum=0
                sumStart = i+1
            end if
        end if
    wend
    print "sequence: ";a$
    print "          ";
    for i=1 to start1-1:   print "   "; :next
    for i= start1 to end1: print "---"; :next
    print
    if end1 >0 then
        print "Maximum sum subsequense: ";start1 ;" to "; end1
    else
        print "Maximum sum subsequense: is empty"
    end if
    print "Maximum sum ";maxsum
    print
end sub
 