c++ - 哪个是找到所有子数组总和的最佳算法？

Question

例如如果

a[3]={1,2,3}

 1,2,3,1+2,2+3,1+2+3  

so my program should print
1
2
3
3
5
8

我知道有一个计算总和的公式。
但我想要的是计算单个总和的有效方法。

建议使用 seg 树？

Answer 1

假设你所说的子数组是指一些作者通常所说的子数组是数组的连续切片，你正在寻找 Kadane's algorithm .

它的工作原理是逐步找到最大的子数组。在搜索的任何给定点，该索引上的最大子数组要么是空数组(和 == 零)，要么由比前一个位置结束的最大子数组多一个元素组成。您跟踪找到的最佳解决方案，以便您可以将子阵列与迄今为止最好的解决方案进行比较，并返回实际的最佳解决方案。

还可以扩展到多个维度。