动态规划-最大子数组和.md

title	date	categories	tags
动态规划：最大子数组和	2022-07-28 16:34:32 -0700	数据结构与算法 动态规划	动态规划

注意

GitHub 的 Markdown 渲染功能不足，文章的完整渲染欢迎来我的 博客小站 查看~~

问题描述

思路与题解

;;;id1 思路 这个题真是我的克星啊，不知道为什么，我脑子一直转不过弯来，总是会想着，要是中间有个小的负数把可以合成一个更大的连续数组隔开了怎么办，该怎么判断，我就一直死脑筋卡在这里了，感觉我也是有点笨笨的，呜呜呜~

但言归正传，看了官方题解后，发现我就真是没转过那个弯来，你就管他是不是一个小负数会把更大的数组隔开，反正只要判断当前数的前面，前面数组的连续和是否对该数有帮助不就行了，有帮助我就收为我有（nums[i] + prev），没有帮助我就另起炉灶（nums[i]），然后再判断我另起炉灶的数和已知的最大和谁大，不断更新最大和就行了，啊啊啊啊，我真是笨呐，为什么这个弯我就没有转过来，我需要老婆的安慰呜呜呜~ ;;;

;;;id1 我的题解

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // return dp(nums);
        return greedy(nums);
    }

private:
    int dp(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n; ++i) {
            if (nums[i-1] > 0) nums[i] += nums[i-1];
        }
        int mx = nums[0];
        for (const int &x : nums) mx = max(mx, x);
        return mx;
    }

    int greedy(vector<int>& nums) {
        // prev 是轮询连续数组
        // mx 维护最大的一个连续数组
        int prev = 0, mx = nums[0];
        for (const int &x : nums) {
            prev = max(x, prev + x);
            mx = max(mx, prev);
        }
        return mx;
    }
};

;;;