23 lines
956 B
Plaintext
23 lines
956 B
Plaintext
procedure main()
|
|
L1 := [-1,-2,3,5,6,-2,-1,4,-4,2,-1] # sample list
|
|
L := [-1,1,2,3,4,-11]|||L1 # prepend a local maximum into the mix
|
|
write(ximage(maxsubseq(L)))
|
|
end
|
|
|
|
link ximage # to show lists
|
|
|
|
procedure maxsubseq(L) #: return the subsequence of L with maximum positive sum
|
|
local i,maxglobal,maxglobalI,maxlocal,maxlocalI
|
|
|
|
maxglobal := maxlocal := 0 # global and local maxima
|
|
|
|
every i := 1 to *L do {
|
|
if (maxlocal := max(maxlocal +L[i],0)) > 0 then
|
|
if /maxlocalI then maxlocalI := [i,i] else maxlocalI[2] := i # local maxima subscripts
|
|
else maxlocalI := &null # reset subsequence
|
|
if maxglobal <:= maxlocal then # global maxima
|
|
maxglobalI := copy(maxlocalI)
|
|
}
|
|
return L[(\maxglobalI)[1]:maxglobalI[2]] | [] # return sub-sequence or empty list
|
|
end
|