Я знаю, как найти максимальную непрерывную сумму подпоследовательности; но иногда существует более одной подпоследовательности с максимальной суммой. Итак, мне нужно найти индекс тех самых длинных подпоследовательностей с максимальной суммой.
Единственное, о чем я подумал - это грубая сила. Какие есть лучшие варианты?
Вот код, который я нашел в rosettacode, который имел точное представление о моей проблеме (но, к сожалению, единственный язык программирования, который я знаю, это Java), но он написан на 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
/*───────────────────────────────────────────────────────────────*/
Результаты:
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