和最大的连续子序列

た入场券 2022-08-09 13:41 249阅读 0赞

[Maximum Subarray Sum][]

2016京东校园招聘数字营销岗的笔试题

**问题描述：**  
一个一维数组同时包含有正整数和负整数，找到数组里和最大的连续子序列  
如：给定数组\{-2, -5, 6, -2, -3, 1, 5, -6\}, 最大和是7，\{6, -2, -3, 1, 1, 5\}

## 方法1 ##

像merge Sort 一样用递归的方法实现，具体可参考[这里][Maximum Subarray Sum]  
时间复杂度O(nlog(n))

## 方法2 ##

这个方法就是方法1的核心  
无论这个数是正数还是负数，这要这个数加在当前的参数“sum\_ending\_here”参数上这个参数还是正数，那个这个数应应该在连续子序列中  
如果*sum\_ending\_here* 小于0， 那么就当前子序列就不是目标子序列，将*sum\_ending\_here* 值0，重新开始找目标子序列  
时间复杂度O(n)

#include <iostream>
    
    using namespace std;
    
    int maxSum1(int *arr, int n)
    {
            int maxS = arr[0];
            int temp = arr[0];
            for(int i = 1; i<n; ++i)
            {
                    temp += arr[i];
                    if(temp>maxS) maxS = temp;
                    else if(temp<0) temp = 0;
            }
            return maxS;
    }

可是此方法对最打和为正数的时候是使用的，若数组的元素全是负就不适用了，换一个角度来考虑，如果“max\_ending\_here”不和0比较，而是将 max\_ending\_here+arr\[i\] 与 arr\[i\] 进行比较，看当前的 max\_ending\_here 对 arr\[i\] 有没有贡献来判断如何更新max\_ending\_here的值

int maxSum2(int *arr, int n)
    {
            int maxS = arr[0];
            int temp = arr[0];
            for(int i = 1; i<n; ++i)
            {
                    if(temp+arr[i]>arr[i])
                            temp += arr[i];
                    else
                            temp = arr[i];
    
                    if(temp > maxS)
                            maxS = temp;
            }
            return maxS;
    }

[Maximum Subarray Sum]: http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/