public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
private int maxCalcVal = Integer.MIN_VALUE;
private int adder = 0;
public int maxSubArray(final List<Integer> A) {
if (A.size() == 0) {
return 0;
}
for(int val : A) {
if (maxCalcVal == Integer.MIN_VALUE) {
maxCalcVal = val;
adder = val;
continue;
}
if (val >= maxCalcVal) {
maxCalcVal = val;
}
if(val > adder && (adder + val) < val) {
adder = val;
continue;
}
adder += val;
if (adder > maxCalcVal) {
maxCalcVal = adder;
}
}
return maxCalcVal;
}
}
Java way of O(n) solution
rajivkris
#1