题目描述

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

下面这个方法的思想就好比赚钱，遇到负数我们自然是希望舍弃。但万一负数后面的正数又很大呢？于是我们就定义一个max去存放最大的值，如果比max大就存入。

具体是如何执行的呢？

遍历，用sum来求得和值（这时候有人问了，如果sum<0怎么办呢？当然是直接清零sum，来表示我们今天没赔钱）

只有在sum为正数的时候才不清空。（也有人就会问，加一个稍小的负数不就变小了嘛，我们不就赔钱了嘛?） 但是我们这里加入了一个存档机制也就是max，我们早就有最大值了，管它后面减小不减小。     

优化：加入判断是否长度为1直接输出结果。

class Solution {public int maxSubArray(int[] nums) {int max=nums[0];int sum = 0;if(nums.length==0){return 0;}for(int i=0;i<nums.length;i++){sum = sum + nums[i];if(max<sum){max = sum;}if(sum<0){sum=0;}}return max;}
}

第二种方法

传送门

这里学习的是里面的代码一，方便深入了解动态规划。定义状态写出状态方程后，问题就迎刃而解。

public class Solution {public int maxSubArray(int[] nums) {//动态规划方法解决问题int n = nums.length;int[] dp = new int[n];if(n==1){return nums[0];}dp[0]=nums[0];int res = nums[0];for(int i=1;i<n;i++){if(dp[i-1]>0){dp[i] = dp[i-1] + nums[i];}else{dp[i] = nums[i];}res = Math.max(res,dp[i]);}return res;}
}