algorithm - 优化算法以计算具有最大总数的子串

Question

什么是优化/智能算法来从以下“n”个数字系列中获得最大总子序列 示例:

Input:             Index   0  1  2  3  4  5  6  7 
                   Series -1  0  3 -2  5 -2  6  1

trials  :          start :4 end :7 total :10
                   start :6 end :7 total :7


Output (Max Total Sub-sequence):  start :2  ,end:7 , total:11 

Answer 1

您可以轻松实现 O(n) 算法；我能想到的有两种方法:

1)DP:

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

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

首先，创建一个前缀和数组，使得prefix[i]是元素0...i的和。现在如果你有一个从 a 到 b 的子序列，那么它的总和显然是 prefix[b] - prefix[a - 1](a = 0 是一个可以轻松处理的特殊情况)。现在假设我们固定了 b，那么最优选择应该最小化 prefix[a - 1]。所以我们可以遍历所有 i，保持最小 prefix[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] );