public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) return 0;
int cursum = Integer.MIN_VALUE;
int maxsum = Integer.MIN_VALUE;
for(int i=0; i<nums.length; ++i){
cursum = cursum>=0 ? Math.max(0,cursum+nums[i]) : Math.max(cursum, nums[i]);
maxsum = Math.max(cursum, maxsum);
}
return maxsum;
}
}
O(n) Java Solution Without DP


It is DP, see the transformation made in https://leetcode.com/discuss/65791/8mscdpsolution