We want to find a subarray with the maximum sum.
For the brute force solution
, we obviously need to keep a global max and a current sum. Then for each number in the array, we search for the contiguous subarray. The time complexity is O(n^2).
Code
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
if (nums == null || nums.length == 0)
return maxSum;
int currentSum = 0;
for (int i = 0; i < nums.length; i++) {
// search the largest contiguous subarray
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum > maxSum) {
maxSum = currentSum;
}
}
currentSum = 0;
}
return maxSum;
}
Complexity
O(n^2) time and O(1) space
Follow Up
Can you do it in linear time?
Analysis
We can use some space to trade off some time. This is an optimization problem. So we want to give DP a try to see if we can spot some overlapping problems. Intuitively, the subproblem's format should look like maxSubarray(int A[], int start, int end) and the original problem maxSubarray(int A[], int 0, int A.length-1). However, this format is hard to think of how the subproblems overlap with each other.
One of the problems with the first format is that it formalizes the subproblems in substrings which are O(n^2) in size. We want to solve by prefix for this problem (removing from the end O(n) size). Defining the subproblems as maxSubarray(int A[], int end) will be a better approach. Then we can write out the recurrence maxSubarray(A[], n) = A[n] + Math.max(maxSubarray(A[], n-1), 0). The topological order is for i from 0 to n-1. The original problem is maxSubarray(A[], A.length-1).
for (int i = 0; i < nums.length; i++)
maxSubarray(A[], n) = A[n] + Math.max(maxSubarray(A[], n-1), 0)
Memoization (Top-down)
int maxSum = Integer.MIN_VALUE;
public int maxSubArray(int[] nums) {
int[] memo = new int[nums.length];
dpHelper(nums, memo, nums.length - 1); // the helper helps in filling out the dp table
return maxSum;
}
private int dpHelper(int[] A, int[] memo, int end) {
if (end == 0) {
memo[end] = A[end];
maxSum = Math.max(maxSum, memo[end]);
return memo[end];
} else {
memo[end] = A[end] + Math.max(dpHelper(A, memo, end-1), 0);
maxSum = Math.max(maxSum, memo[end]);
return memo[end];
}
}
Tabulation (Bottom-up)
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int[] memo = new int[nums.length];
// initialization
memo[0] = nums[0];
// topo order
for (int i = 1; i < nums.length; i++) {
// recurrence of dp
memo[i] = nums[i] + Math.max(memo[i-1], 0);
maxSum = Math.max(maxSum, memo[i]);
}
// solve the original problem
return maxSum;
}
Sometimes it is easier to create memo[A.length+1]. (not in this simple case)
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int[] memo = new int[nums.length + 1];
// initialization
memo[0] = maxSum;
// topo order
for (int i = 0; i < nums.length; i++) {
// recurrence of dp
memo[i+1] = nums[i] + Math.max(memo[i], 0);
maxSum = Math.max(maxSum, memo[i+1]);
}
return maxSum;
}
Complexity
Time = #subproblems x time/subproblem = n * O(1) = O(n)
Space = O(n)
