C++ 查找数组中元素总和最大的子序列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3733251/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the subsequence with largest sum of elements in an array
提问by brett
I recently interviewed with a company and they asked me to write an algorithm that finds the subsequence with largest sum of elements in an array. The elements in the array can be negative. Is there a O(n) solution for it? Any good solutions are very much appreciated.
我最近采访了一家公司，他们让我写一个算法，找出数组中元素总和最大的子序列。数组中的元素可以为负数。有 O(n) 解决方案吗？非常感谢任何好的解决方案。
回答by Matthew
If you want the largest sum of sequential numbers then something like this might work:
如果你想要最大的序列号总和，那么这样的事情可能会奏效：
$cur = $max = 0;
foreach ($seq as $n)
{
$cur += $n;
if ($cur < 0) $cur = 0;
if ($cur > $max) $max = $cur;
}
That's just off the top of my head, but it seems right. (Ignoring that it assumes 0 is the answer for empty and all negative sets.)
这只是我的头顶，但似乎是对的。（忽略它假设 0 是空集和所有负集的答案。）
Edit:
编辑：
If you also want the sequence position:
如果您还想要序列位置：
$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);
There might be a more concise way to do it. Again, it has the same assumptions (at least one positive integer). Also, it only finds the first biggest sequence.
可能有更简洁的方法来做到这一点。同样，它具有相同的假设（至少一个正整数）。此外，它只找到第一个最大的序列。
Edit: changed it to use max_j(exclusive) instead of max_len.
编辑：将其更改为使用max_j（独占）而不是max_len.
回答by Eyal Schneider
If you mean longest increasing subsequence, see codaddict's answer.
如果您的意思是最长递增子序列，请参阅codacci的答案。
If on the other hand you mean finding the sub array with maximum sum(makes sense only with negative values), then there is an elegant, dynamic programming style linear time solution:
另一方面，如果您的意思是找到具有最大和的子数组（仅对负值有意义），那么有一个优雅的动态编程风格线性时间解决方案：
回答by Shobhit
Try the following code:
试试下面的代码：
#include <stdio.h>
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();
}
回答by codaddict
I assume you mean longest increasing subsequence.
我假设您的意思是最长递增子序列。
There is no O(n)solution for that.
没有O(n)解决方案。
A very naive solution would be to create a duplicate array, sort it in O(NlogN)and then find the LCSof the sorted array and original array which takes O(N^2).
一个非常天真的解决方案是创建一个重复的数组，将其排序O(NlogN)，然后找到LCS已排序数组和原始数组的O(N^2).
There also is a direct DP based solution similar to LCSwhich also takes O(N^2), which you can see here.
还有一个基于直接 DP 的解决方案，类似于LCSwhich also take O(N^2)，你可以在这里看到。
But if you meant longest increasing sequence (consecutive). This can be done in O(N).
但是，如果您的意思是最长递增序列（连续）。这可以在O(N).
回答by asim kadav
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);
}
回答by vran freelancer
This problem can be solved two different ways.
这个问题可以用两种不同的方式解决。
The first approach is have two variables called sumand MaxSum.
第一种方法是有两个变量，称为sum和MaxSum。
We will keep on adding values to the sum and will compare with the MaxSum, if the value for the sum is greater than the MaxSum - will assign sum value to the MaxSum
If during the process the value for the sum goes below 0, we will reset the sum and will start adding new number from the next index on-wards. The sample code for the above solution is provided as below:
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); }
我们将继续向总和添加值并与 MaxSum 进行比较，如果总和的值大于 MaxSum - 将总和值分配给 MaxSum
如果在此过程中总和的值低于 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); }
The second approach to solve this problem is that we will go through each and every element in an array. We will have same 2 variables of sum and MaxSum.
解决这个问题的第二种方法是我们将遍历数组中的每个元素。我们将有相同的 2 个变量 sum 和 MaxSum。
First we will compare the addition of sum with the next array element and the sum itself. Who ever is greater - that value will be stored in the sum variable.
Next we will compare the values of sum and MaxSum and whoever has greater value - we will save that value in the MaxSum variable. The sample code is as mentioned below:
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; }
首先，我们将比较 sum 与下一个数组元素的相加以及 sum 本身。谁更大 - 该值将存储在 sum 变量中。
接下来，我们将比较 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; }
回答by whizvids
If you are asking what is a contiguous subsequence for which the sum is maximum, I have found 4 algos so far:-
如果你问什么是总和最大的连续子序列，到目前为止我已经找到了 4 个算法：-
Brute-force: Find all possible sums using nested loops and keep updating the maxSum if you find a sum greater than previous set value of maxSum. The time complexity is O(n^2)
Dynamic Programming Solution: This is a remarkably elegant solution which I found on StackOverflow itself - https://stackoverflow.com/a/8649869/2461567v- Time complexity : O(n), Space complexity : O(n)
DP without memory - Kadane Algorithm -https://en.wikipedia.org/wiki/Maximum_subarray_problem- Time complexity : O(n), Space complexity : O(1)
Divide and Conquer Solution - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdfTime complexity : O(nlgn)
蛮力：使用嵌套循环查找所有可能的总和，如果发现总和大于先前设置的 maxSum 值，则继续更新 maxSum。时间复杂度为 O(n^2)
动态编程解决方案：这是我在 StackOverflow 上发现的一个非常优雅的解决方案 - https://stackoverflow.com/a/8649869/2461567v- 时间复杂度：O(n)，空间复杂度：O(n)
无记忆的 DP - Kadane 算法 - https://en.wikipedia.org/wiki/Maximum_subarray_problem- 时间复杂度：O(n)，空间复杂度：O(1)
分而治之的解决方案 - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf时间复杂度：O(nlgn)
回答by snowgoose
C function looks like this:
C 函数看起来像这样：
int largest(int arr[], int length)
{
int sum= arr[0];
int tempsum=0;
for(int i=0;i<length;i++){
tempsum+=arr[i];
if(tempsum>sum)
sum=tempsum;
if(tempsum<0)
tempsum=0;
}
return sum;
}
