题目
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [0] 输出：0
示例 4：
输入：nums = [-1] 输出：-1
示例 5：
输入：nums = [-100000] 输出：-100000
解题
方法一：暴力（会超时）
class Solution { public: int maxSubArray(vector<int>& nums) { int res=INT32_MIN; int tmp=0; for(int i=0;i<nums.size();i++){ tmp=0; for(int j=i;j<nums.size();j++){ tmp+=nums[j]; res=tmp>res?tmp:res; } } return res; } };
方法二：贪心
遍历nums，从头开始用tmp累积，如果tmp一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积tmp了，因为已经变为负数的tmp，只会拖累总和
class Solution { public: int maxSubArray(vector<int>& nums) { int res=INT_MIN; int tmp=0; for(int i=0;i<nums.size();i++){ tmp+=nums[i]; res=max(tmp,res); // 取区间累计的最大值（相当于不断确定最大子序终止位置） if(tmp<=0) tmp=0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和 } return res; } };
方法三：动态规划
class Solution { public: int maxSubArray(vector<int>& nums) { int pre=0; int res=nums[0]; for(int num:nums){ pre=max(pre+num,num); //状态转移方程 res=max(res,pre); //更新最大值 } return res; } };
java
class Solution { public int maxSubArray(int[] nums) { if(nums.length==1) return nums[0]; int pre=0; int res=nums[0]; for(int i=0;i<nums.length;i++){ pre=Math.max(pre+nums[i],nums[i]); res=Math.max(res,pre); } return res; } }
