题目地址：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
贪心思想： 我们利用贪心思想解决这个问题，最容易想到的就是不断累加的过程。当累加的和小于0时，说明对最终结果是负贡献，就从下一个数重新开始，同时更新最大和的值，当累加和大于0时，说明是正贡献，将下一个数值加入和中，同时更新最大和的值。
动态规划
class Solution { public: int Max(int a, int b) { if(a >= b) return a; else return b; } int maxSubArray(vector<int>& nums) { if(nums.size() < 1) return 0; int sum = nums[0]; for(int i = 1; i < nums.size(); i++) { if(nums[i-1] > 0) { nums[i] += nums[i-1]; } sum = Max(nums[i], sum); } return sum; } };
贪心法
class Solution { public: int maxSubArray(vector<int>& nums) { if(nums.size() < 1) return 0; int resSum = INT_MIN; int curSum = 0; for(int i = 0; i < nums.size(); i++) { if(curSum > 0) { curSum += nums[i]; } else { curSum = nums[i]; } if(curSum > resSum) resSum = curSum; } return resSum; } };
原文：https://www.cnblogs.com/wzw0625/p/12571893.html