动态规划：最大子数组和 - 动态规划 - 数据结构与算法 | Aayu Yain = 学无止境 = 世界上大部分事，都没太大意义。真理与热爱除外

# 问题描述

# 思路与题解

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

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

	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;
	}
	};