LeetCode刷题笔记（贪心）：maximum-subarray-蒲公英云

LeetCode刷题笔记（贪心）：maximum-subarray

转载请注明作者和出处：http://blog.csdn.net/u011475210
代码地址：https://github.com/WordZzzz/Note/tree/master/LeetCode
刷题平台：https://www.nowcoder.com/ta/leetcode
题库：Leetcode经典编程题
编者：WordZzzz

- 题目描述
- 解题思路
- C版代码实现

题目描述

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.

在一个数组中找到连续的子数组（至少包含一个数字），这个数组的总和最大。例如，给定数组[-2,1，-3,4，-1,2,1，-5,4]，连续的子数组[4，-1,2,1]具有最大的和= 6。更多的练习：如果你已经找到了O（n）的解决方案，尝试使用分而治之的方法编码另一个解决方案，这是更微妙的。

解题思路

从头开始累加，直到和为负。此时前面这段不能给后面的串带来正收益，应舍弃，sum清零，然后再开始统计最大的sum。算法时间复杂度O(n)。

题目中说可以尝试一下分治法，我是没想出来，后来看了leetcode上大神的代码才恍然大悟知道要怎么写。

For each subarray, calculate four attributes:

mx (largest sum of this subarray), 
lmx(largest sum starting from the left most element), 
rmx(largest sum ending with the right most element), 
sum(the sum of the total subarray).

算法复杂度作者竟然说是O(n)，但是我觉得是O(logn)？

class Solution {
public:
    void maxSubArray(vector<int>& nums, int l, int r, int& mx, int& lmx, int& rmx, int& sum) {
        if (l == r) {
            mx = lmx = rmx = sum = nums[l];
        }
        else {
            int m = (l + r) / 2;
            int mx1, lmx1, rmx1, sum1;
            int mx2, lmx2, rmx2, sum2;
            maxSubArray(nums, l, m, mx1, lmx1, rmx1, sum1);
            maxSubArray(nums, m + 1, r, mx2, lmx2, rmx2, sum2);
            mx = max(max(mx1, mx2), rmx1 + lmx2);
            lmx = max(lmx1, sum1 + lmx2);
            rmx = max(rmx2, sum2 + rmx1);
            sum = sum1 + sum2;
        }
    }
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int mx, lmx, rmx, sum;
        maxSubArray(nums, 0, nums.size() - 1, mx, lmx, rmx, sum);
        return mx;
    }
};

C++版代码实现

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if(A == NULL || n == 0)
            return false;
        int sum = A[0];
        int maxSum = A[0];
        for(int i = 1; i < n; ++i){
            if(sum < 0)
                sum = 0;
            sum += A[i];
            maxSum = max(sum, maxSum);
        }
        return maxSum;
    }
};