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

╰半橙微兮° 2022-06-01 11:19 106阅读 0赞

--------------------

*  **转载请注明作者和出处：[http://blog.csdn.net/u011475210][http_blog.csdn.net_u011475210]**
 *  **代码地址：[https://github.com/WordZzzz/Note/tree/master/LeetCode][https_github.com_WordZzzz_Note_tree_master_LeetCode]**
 *  **刷题平台：[https://www.nowcoder.com/ta/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;
        }
    };

**系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～**

**完的汪(∪｡∪)｡｡｡zzz**

[http_blog.csdn.net_u011475210]: http://blog.csdn.net/u011475210
[https_github.com_WordZzzz_Note_tree_master_LeetCode]: https://github.com/WordZzzz/Note/tree/master/LeetCode
[https_www.nowcoder.com_ta_leetcode]: https://www.nowcoder.com/ta/leetcode