查找数组中元素总和最大的子序列

我最近采访了一家公司，他们让我写一个算法，找到数组中元素总和最大的子序列。 数组中的元素可以是负数。 是否有O（n）解决方案？ 非常感谢任何好的解决方案。

Answer 1

如果你想要最大的序列数之和，那么像这样的东西可能会起作用：

$cur = $max = 0; foreach ($seq as $n) { $cur += $n; if ($cur < 0) $cur = 0; if ($cur > $max) $max = $cur; } 

这只是我的头脑，但似乎是正确的。 （忽略它假定0是空和所有负集的答案。）

编辑：

如果您还想要序列位置：

 $cur = $max = 0; $cur_i = $max_i = 0; $max_j = 1; foreach ($seq as $i => $n) { $cur += $n; if ($cur > $max) { $max = $cur; if ($cur_i != $max_i) { $max_i = $cur_i; $max_j = $max_i + 1; } else { $max_j = $i + 1; } } if ($cur < 0) { $cur = 0; $cur_i = $i + 1; } } var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max); 

可能有一种更简洁的方法来做到这一点。 同样，它具有相同的假设（至少一个正整数）。 此外，它只找到第一大序列。

编辑：将其更改为使用max_j （独占）而不是max_len 。

Answer 2

如果你的意思是增加最长的子序列，请参阅codaddict的答案。

另一方面，如果你的意思是找到具有最大总和的子数组 （仅对负值有意义），那么有一个优雅，动态的编程风格线性时间解决方案：

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Answer 3

请尝试以下代码：

 #include  int main(void) { int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3}; int cur = arr[0] >= 0? arr[0] : 0, max = arr[0]; int start = 0, end = 0; int i,j = cur == 0 ? 1 : 0; printf("Cur\tMax\tStart\tEnd\n"); printf("%d\t%d\t%d\t%d\n",cur,max,start,end); for (i = 1; i < 10; i++) { cur += arr[i]; if (cur > max) { max = cur; end = i; if (j > start) start = j; } if (cur < 0) { cur = 0; j = i+1; } printf("%d\t%d\t%d\t%d\n",cur,max,start,end); } getchar(); } 

Answer 4

我认为你的意思是增加最长的子序列 。

没有O(n)解决方案。

一个非常天真的解决方案是创建一个重复的数组，在O(NlogN)对它进行排序，然后找到排序数组的LCS和原始数组，取O(N^2) 。

还有一个类似于LCS的直接基于DP的解决方案，它也需要O(N^2) ，你可以在这里看到。

但如果你的意思是增加最长的序列（连续）。 这可以在O(N) 。

Answer 5

 void longsub(int a[], int len) { int localsum = INT_MIN; int globalsum = INT_MIN; int startindex = 0,i=0; int stopindex = 0; int localstart = 0; for (i=0; i < len; i++) { if (localsum + a[i] < a[i]) { localsum = a[i]; localstart = i; } else { localsum += a[i]; } if (localsum > globalsum) { startindex = localstart; globalsum = localsum; stopindex = i; } } printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum); } 

Answer 6

这个问题可以通过两种不同的方式解决。

第一种方法有两个变量，称为sum和MaxSum 。

1. 如果和的值大于MaxSum，我们将继续向总和添加值并与MaxSum进行比较 – 将总和值分配给MaxSum

2. 如果在此过程中总和的值低于0，我们将重置总和并开始从下一个索引中添加新数字。 上述解决方案的示例代码如下：

    private static void FindMaxSum(int[] array) { int sum = 0; int MaxSum = 0; for (int i = 0; i < array.Length; i++) { sum += array[i]; if (sum > MaxSum) { MaxSum = sum; } else if (sum < 0) { sum = 0; } } Console.WriteLine("Maximum sum is: " + MaxSum); } 

解决这个问题的第二种方法是我们将遍历数组中的每个元素。 我们将有相同的2个sum和MaxSum变量。

1. 首先，我们将比较sum与下一个数组元素和sum本身的相加。 谁曾经更大 - 该值将存储在sum变量中。

2. 接下来，我们将比较sum和MaxSum的值以及具有更大值的人 - 我们将该值保存在MaxSum变量中。 示例代码如下所述：

    private static void FindMaxSum(int[] array) { int sum = array[0], Maxsum = array[0]; for (int i = 1; i < array.Length; i++) { sum = Max(sum + array[i], array[i]); Maxsum = Max(sum, Maxsum); } Console.WriteLine("Maximum sum is: " + Maxsum); } private static int Max(int a, int b) { return a > b ? a : b; } 

Answer 7

如果你问的是什么是总和最大的连续子序列，我到目前为止找到了4个algos： –

1. 暴力：使用嵌套循环查找所有可能的总和，如果找到的总和大于之前设置的maxSum值，则继续更新maxSum。 时间复杂度为O（n ^ 2）

2. 动态编程解决方案：这是我在StackOverflow上发现的非常优雅的解决方案 – https://stackoverflow.com/a/8649869/2461567v – 时间复杂度：O（n），空间复杂度：O（n）

3. 没有内存的DP – Kadane算法 – https://en.wikipedia.org/wiki/Maximum_subarray_problem – 时间复杂度：O（n），空间复杂度：O（1）

4. 分而治之的解决方案 – http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf时间复杂度：O（nlgn）

Answer 8

C函数看起来像这样：

 int largest(int arr[], int length) { int sum= arr[0]; int tempsum=0; for(int i=0;isum) sum=tempsum; if(tempsum<0) tempsum=0; } return sum; }