描述
给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
注意事项
子数组最少包含一个数
样例
给出数组
[−2,2,−3,4,−1,2,1,−5,3]
,符合要求的子数组为[4,−1,2,1]
,其最大和为6
挑战
要求时间复杂度为O(n)
代码
- Greedy
public class Solution {
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
// 数组不存在,最大和即为0
return 0;
}
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
max = Math.max(max, sum);
sum = Math.max(sum, 0);
}
return max;
}
}
- Prefix Sum
public class Solution {
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
return 0;
}
// 初值的设定要注意
int max = Integer.MIN_VALUE;
int sum = 0;
int minSum = 0;
for (int i = 0; i < A.length; i++) {
sum += A[i];
// minSum 的更新要放在 max 后面
max = Math.max(max, sum - minSum);
minSum = Math.min(minSum, sum);
}
return max;
}
}