java - 最长序列的最大连续子序列和？

Question

我知道如何找到最大连续子序列和；但有时会有多个具有最大总和的子序列。因此，我需要找到具有最大和的最长子序列的索引。我唯一想到的就是暴力。还有什么更好的选择？

这是我在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

Answer 1

如果这是家庭作业，我建议您看一下动态规划算法。特别是，您可以简化 Smith-Waterman 本地字符串对齐的步骤之一，以准确完成此处所需的操作。关键是要阅读最佳子结构的概念，并问自己，是否涉及某种子问题，我可以仅使用序列中每个点的局部信息来解决？