53. Maximum Subarray (kadane-algo
Last updated
Last updated
T: O(n)
S: O(1)
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int num : nums) {
sum += num;
max = Math.max(max, sum);
if (sum < 0) {
sum = 0;
}
}
return max;
}
}
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int num : nums) {
sum += num;
max = Math.max(max, sum);
sum = Math.max(0, sum); // [-1] -> should remain [-1], so put here
}
return max;
}
}
or
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
int sum = 0;
for (int num : nums) {
// sum += num;
// add 後, 如果反而比較小, 就丟棄之前的 sum
sum = Math.max(sum + num, num); // [-1] -> should remain [-1], so put here
max = Math.max(max, sum);
}
return max;
}
}