今天来看看这道题,介绍两种解法
第一种动态规划,代码如下
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)全球极客挚爱的技术成长平台