52.最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为6。

示例2：

输入：nums = [1]
输出：1

示例3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1<=nums.length<=10^5
• -10^4<=nums[i]<=10^4

进阶：如果你已经实现复杂度为O(n)的解法，尝试使用更为精妙的分治法求解

---

解题思路

贪心思路

局部最优：当前"连续和"为负数时放弃，从下一个元素开始重新计算连续和
全局最优：最大连续和

---

代码实现

核心模式

class Solution{
    
public:
    int maxSubArray(vector<int>& nums){
        // Two Inportant points
        // First: give up when the sum of nums is negative 
        // Second: update result when the count gather than result
        int result = INT_MIN;
        int count = 0;

        for (int i = 0; i < nums.size(); i++){
            count += nums[i];
            if (count > result) result = count;
            if (count < 0) count = 0;
        }

        return result;
    }
};

ACM模式

"greed.h"

#include <iostream>
#include "greed.h"

class Solution{
    
public:
    int maxSubArray(vector<int>& nums){
        // Two Inportant points
        // First: give up when the sum of nums is negative 
        // Second: update result when the count gather than result
        int result = INT_MIN;
        int count = 0;

        for (int i = 0; i < nums.size(); i++){
            count += nums[i];
            if (count > result) result = count;
            if (count < 0) count = 0;
        }

        return result;
    }
};

int main(){
    vector<int> case1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    vector<int> case2 = {1};
    vector<int> case3 = {5, 4, -1, 7, 8};

    Solution solution;
    int result1 = solution.maxSubArray(case1);
    int result2 = solution.maxSubArray(case2);
    int result3 = solution.maxSubArray(case3);

    cout << "Result1 = " << result1 << endl;
    cout << "Result2 = " << result2 << endl;
    cout << "Result3 = " << result3 << endl;

    return 0;
}

• 输出

Result1 = 6
Result2 = 1
Result3 = 23

• 动态规划解法