Given an array of integers, find a contiguous subarray which has the largest sum.
Example
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
Analysis
DP和Greedy均可进行求解，不过还是更推荐使用DP，因为Greedy很多情况下都是不正确的。
Dynamic Programming:
maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];
Kadane's Algorithm
Solution
Brute-force Compare all subarray sum (119 ms 2.49% AC)
// Compare all subarray sum: O(n^2)
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int sum;
for (int i = 0; i < nums.length; i++) {
sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
maxSum = Math.max(sum, maxSum);
}
}
return maxSum;
}
}
Improvement O(n) (7ms 93.68% AC)
class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum = sum > 0 ? nums[i] + sum : nums[i];
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
}
Dynamic Programming
// Dynamic Programming: O(n)
// Similar idea to Greedy Algorithm
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n]; //dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
Greedy Algorithm
// Greedy Algorithm: O(n)
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
int max = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < length; i++) {
sum = sum + nums[i];
max = Math.max(sum, max);
sum = Math.max(sum, 0);
}
return max;
}
}
Prefix Sum
public class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int max = Integer.MIN_VALUE, min = 0;
int prefixSum = 0;
for(int i = 0; i < nums.length; i++){
prefixSum += nums[i];
max = Math.max(max, prefixSum - min);
min = Math.min(min, prefixSum);
}
return max;
}
}
Kadane's Alogrithm
public class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int cur = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
cur = Math.max(nums[i], cur + nums[i]);
max = Math.max(max, cur);
}
return max;
}
}