描述
給定一個(gè)整數(shù)數(shù)組，找到一個(gè)具有最大和的子數(shù)組米同，返回其最大和骇扇。
注意事項(xiàng)
子數(shù)組最少包含一個(gè)數(shù)
樣例
給出數(shù)組
[?2,2,?3,4,?1,2,1,?5,3]，符合要求的子數(shù)組為[4,?1,2,1]面粮，其最大和為6
挑戰(zhàn)
要求時(shí)間復(fù)雜度為O(n)
代碼
- Greedy
public class Solution {
public int maxSubArray(int[] A) {
if (A == null || A.length == 0){
// 數(shù)組不存在少孝，最大和即為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;
}
// 初值的設(shè)定要注意
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;
}
}
