Typical DP:1
2
3
4
5
6
7
8
9
10
11public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; ++i) {
dp[i] = (dp[i-1] > 0 ? dp[i-1] : 0) + nums[i];
max = Math.max(max, dp[i]);
}
return max;
}
Kadane. Similar thought, more distinguishable by name1
2
3
4
5
6
7
8
9public int maxSubArray(int[] nums) {
int maxEndHere = nums[0], maxSoFar = nums[0];
for (int i = 1; i < nums.length; ++i) {
maxEndHere = Math.max(nums[i], maxEndHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndHere);
}
return maxSoFar;
}
}