做网站的好处在哪里百度信息

今天来看看这道题，介绍两种解法

第一种动态规划，代码如下

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {// 计算当前最大前缀和pre = Math.max(pre + x, x);// 更新最大前缀和maxAns = Math.max(maxAns, pre);}return maxAns;}
}

第二种前缀和，这种方法是评论里的大佬想出来的，可以学习一下，只要思想就是分别维护三个变量，前缀和、最小前缀和、前缀和 - 最小前缀和，其中答案就是前缀和 - 最小前缀和里最大的那个数，看代码和动态规划的思想有点类似，代码如下

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE, preSum = 0, minPreSum = 0;for (int num : nums) {// 计算前缀和preSum += num;// 计算前缀和 - 最小前缀和ans = Math.max(ans, preSum - minPreSum);// 记录最小前缀和minPreSum = Math.min(minPreSum, preSum);}return ans;}
}

题目链接：题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台