问优化算法计算最大合计的子串

EN

您可以很容易地实现O(n)算法；我可以想到两种方法：

1) DP:

设dpi是在元素i结束的最大子序列的长度，然后是dp[0] = element[0]。对于每个i，dp[i] = max( dp[i - 1] + element[i], element[i] )。这是因为您有两个选择，要么将当前元素添加到先前的最大子序列中，要么创建一个新的元素。取所有I的最大值，这就是你的答案。您可以通过轻松跟踪更改来找到开头和结尾。

2)一个简单直观的算法：

首先，创建一个前缀和数组，这样前缀就是元素0...i的总和。现在，如果你有一个从a到b的子序列，那么它的和显然是prefix[b] - prefix[a - 1]的(a=0是一个很容易处理的特例)。现在假设我们固定了b，那么最优选择应该最小化前缀a- 1。所以我们可以迭代所有的i，保持到目前为止的最小前缀j。答案就是所有步骤的最大值，每一步：prefix[i] - prefix[j]。

下面是伪代码：

// Compute prefix sum array easily and trivially ( ask me if you want how )

int curMin = 0, answer = - INFINITY;

for i = 0 to n - 1

      answer = max( answer, prefix[i] - curMin );

      curMin = min( curMin, prefix[i] );

存在一种线性算法。例如，请参阅此http://wordaligned.org/articles/the-maximum-subsequence-problem