深信服手撕算法题—连续子数组的最大和

连续子数组的最大和

题目描述如下： 第一次我做的思路是用两个for循环遍历，写完以后面试官说你这么写是有问题的，会超时。由于面试时间比较紧张，就叫我私底下再好好想想。 最好的做法是用动态规划算法 时间复杂度为0(N)

public int maxSubArray(int[] nums) { int[]dp = new int[nums.length]; //动态规划列表 dp， dp[0] = nums[0]; int res = nums[0];//全局最大值 for(int i = 1;i<nums.length;i++){ dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);//dp[i] 代表以元素 nums[i]为结尾的连续子数组最大和 //如果dp[i-1]<0,则不加；如果dp[i-1]>0,则加上该值，进行更新 res = Math.max(res,dp[i]); //更新全局最大值 } return res; }

也可以只用一个res变量解决该问题：

public int maxSubArray(int[] nums) { int res = nums[0];//全局最大值 for(int i = 1;i<nums.length;i++){ nums[i] += Math.max(0,nums[i-1]); res = Math.max(res,nums[i]); } return res; }