首页 > 代码库 > [C++]LeetCode: 58 Maximum Subarray

[C++]LeetCode: 58 Maximum Subarray

题目:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [?2,1,?3,4,?1,2,1,?5,4],
the contiguous subarray [4,?1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Anwser 1: Kadane算法

思路:把数组里元素不断往结果里添加,直到sum的值小于0,这时将sum重置为0,同时始终维护一个ans变量,表示子串的和最大值(会获得添加过程中的最大值)。

关于Kadane算法的正确性说明:
       对于array[1...n],如果array[i...j]就是满足和最大的子串,那么对于任何k(i<=k<=j),我们有array[i...k]的和大于0。因为如果存在k使得array[i...k]的和小于0,那么我们就有array[k+1...j]的和大于array[i...j],这与我们假设的array[i...j]就是array中和最大子串矛盾。
    其次,我们可以将数组从左到右分割为若干子串,使得除了最后一个子串之外,其余子串的各元素之和小于0,且对于所有子串array[i...j]和任意k(i<=k<j),有array[i...k]的和大于0。此时我们要说明的是,满足条件的和最大子串,只能是上述某个子串的前缀,而不可能跨越多个子串。

Attention:

1.sum添加必须从A[0]开始,如果A[0]是负值,则舍弃。

2.判断sum 低于0,则重置0

sum = max(sum, 0);

3.顺序很重要,先比较得到一个较大值,再看是否需重置sum. 维护ans是数组内最大和。

ret = max(ret, sum);
//只把大于0的添加进子序列。
sum = max(sum, 0);

复杂度:O(N)

AC Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        //Idea is very simple. Basically, keep adding each integer to the sequence until the sum drops below 0. If sum is negative, then should reset the sequence.
        int ret = A[0];
        int sum = 0;
        
        for(int i = 0; i < n; i++)
        {
            //必须从A[0]开始加,如果A[0]小于0,则后面判断时舍去A[0]
            sum += A[i];
            ret = max(ret, sum);
            //只把大于0的添加进子序列。
            sum = max(sum, 0);
        }
        return ret;
        
    }
};


Anwser 2: 分治法

分治法:最大子串和的区间有以下三种情况(low,high分别为左右边界,mid为(low+high)/2):

(1) 区间完全在 A[low,mid-1]
(2) 区间完全在 A[mid+1,high]
(3) 区间包含有 A[mid]

按照这三种情况一直递归下去即可。


Step:

1.  找到数组中间元素,最大子串可能包含或者不包含中间元素。

2.  分开计算

     2.1 如果不包含中间元素,继续在A[low,mid-1] 和 A[mid+1,high]用相同算法查找最大和子串。

     2.2 如果包含,则最大子串,将包含左串的最大后缀和右串的最大前缀

3.  返回三个结果的最大值。


Attention:

1. 注意如何计算最大左后缀和最大右前缀。

2. 注意递归求解左区间和右区间时的范围。

//计算左区间和右区间
        int leftans = maxSubArray_helper(A, left, middle);
        int rightans = maxSubArray_helper(A, middle+1, right);
3. 注意递归终止条件。

if(left == right) return A[left];

4. 包含全部元素比较好考虑,不会落下一些值。把middle加入左区间中。


复杂度:O(Nlog(n))


AC Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if(n == 0) return 0;
        maxSubArray_helper(A, 0, n-1);
    }
    
    int maxSubArray_helper(int A[], int left, int right)
    {
        if(left == right) return A[left];
        int middle = left + (right - left)/2;
        
        //计算左区间和右区间
        int leftans = maxSubArray_helper(A, left, middle);
        int rightans = maxSubArray_helper(A, middle+1, right);
        
        //计算含中间元素的区间
        int leftmax = A[middle];
        int rightmax = A[middle+1];
        
        int tmp = 0;
        for(int i = middle; i >= left; i--)
        {
            tmp += A[i];
            leftmax = max(leftmax, tmp);
        }
        
        tmp = 0;
        for(int i = middle+1; i <= right; i++)
        {
            tmp += A[i];
            rightmax = max(rightmax, tmp);
        }
        
        return max(max(leftans, rightans), leftmax + rightmax);
    }
};


[C++]LeetCode: 58 Maximum Subarray