Reference: LeetCode
Difficulty: Easy

My Post: Easy-Understand Java Solutions with Explanations (B-F, Divide-And-Conquer, DP)

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example: 

1
2
3
4
5
6
Input: [-5]
Output: -5

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up: If you have figured out the $O(N)$ solution, try coding another solution using the divide and conquer approach, which is more subtle.

Analysis

Most Stupid Solution

For each element, we construct all possible subarrays starting from this element. Totally there are at most $N^2$ subarrays. Also, calculating the sum of each subarray takes $O(N)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxSubArray(int[] nums) {
  int n = nums.length;
  int maxSum = Integer.MIN_VALUE;
  for (int i = 0; i < n; ++i) {
    for (int j = i; j < n; ++j) {
      int sum = 0;
      for (int k = i; k <= j; ++k) {
        sum += nums.get(k);
      }
      maxSum = Math.max(maxSum, sum);
    }
  }
  return maxSum;
}

Time: $O(N^3)$
Space: $O(1)$

Brute-Force

Why did you calculate the sum separately?

Note: In the inner loop, start from i + 1. Don’t initialize sum as $0$ and start from i.

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
  int n = nums.length;
  int maxSum = Integer.MIN_VALUE; // can't be 0
  for (int i = 0; i < n; ++i) { // starts at i
    int sum = nums[i];
    maxSum = Math.max(maxSum, sum);
    for (int j = i + 1; j < n; ++j) { // starts from the next element
      sum += nums[j];
      maxSum = Math.max(maxSum, sum);
    }
  }
  return maxSum;
}

Time: $O(N^2)$
Space: $O(1)$

Divide and Conquer

Divide-and-conquer consider 3 cases:

  • Case 1: Subarray in the left half -> leftSum
  • Case 2: Subarray in the right half -> rightSum
  • Case 3: Subarray crosses the middle -> crossSum

We need to compare three max values: leftSum, rightSum, and crossSum. By constructing the crossSum, we propagate from the right-end of the left subarray [lo, mid] and from the left-end of the right subarray [mid + 1, hi]. In each direction, we are continuously updating the maximum sum.

1
2
3
4
5
6
// Example
index: 0  1  2  3  4  5  6
      -5  7  3 -1  1  2  3
               mid
For the left half, we go through from -1 to -5. The maximum sum is (-1) + 3 + 7 = 9.
It can't be 3 + 7 = 10, because -1 must be included (crossing).

BTW, Index lo/hi/mid Caveat:

Write the condition as if (lo == hi) (stops at one element) or if (lo >= hi) (stops at $0$ element). Why?

Write the subproblem as [lo, mid] and [mid + 1, hi], which is not like binary search (hi = mid - 1 and lo = mid + 1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public int maxSubArray(int[] nums) {
  int n = nums.length;
  return maxSubArray(nums, 0, n - 1);
}

private int maxSubArray(int[] nums, int lo, int hi) {
  if (lo == hi) { // base case: one number
    return nums[lo];
  }
  // divide
  int mid = lo + (hi - lo) / 2;
  // conquer
  int leftSum = maxSubArray(nums, lo, mid);
  int rightSum = maxSubArray(nums, mid + 1, hi);
  // combine
  int crossSum = crossSum(nums, lo, hi);
  return Math.max(crossSum, Math.max(leftSum, rightSum));
}

// invariant: lo < hi (left part and right part both have at least 1 element
private int crossSum(int[] nums, int lo, int hi) {
  int mid = lo + (hi - lo) / 2;
  // left
  int leftSum = 0, leftMax = Integer.MIN_VALUE; // the invariant means that leftMax and rightMax will be updated
  for (int i = mid; i >= lo; --i) {
    leftSum += nums[i];
    leftMax = Math.max(leftMax, leftSum);
  }
  // right
  int rightSum = 0, rightMax = Integer.MIN_VALUE;
  for (int i = mid + 1; i <= hi; ++i) {
    rightSum += nums[i];
    rightMax = Math.max(rightMax, rightSum);
  }
  return leftMax + rightMax;
}

Another version, initialize sums and max values as the first element.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int crossSum(int[] nums, int lo, int hi, int mid) {
  // left
  int leftSum = nums[mid]; // okay because 0 <= lo <= mid < hi <= n - 1
  int leftMax = leftSum;
  for (int i = mid - 1; i >= lo; --i) {
    leftSum += nums[i];
    leftMax = Math.max(leftMax, leftSum);
  }
  // right
  int rightSum = nums[mid + 1]; // lo < hi is guaranteed
  int rightMax = rightSum;
  for (int i = mid + 2; i <= hi; ++i) {
    rightSum += nums[i];
    rightMax = Math.max(rightMax, rightSum);
  }
  return leftMax + rightMax;
}

Time: $O(N\log{N})$ since $T(N) = 2T(N/2) + O(N)$.
Space: $O(\log{N})$

DP

Suppose we know the maximum subarray ending at $i$ (inclusive). We denote SUM(i) as the maximum sum of a subarray ending at index $i$ and denote OPT(i) as the maximum sum in the subarray $[0, i]$. Our final result is OPT(n - 1). (notice the difference since it is very trivial)

For an element nums[i], we have two choices: Appending it to a previous subarray SUM(i - 1) or start a new subarray from itself. Then we can write the recurrence for SUM(i) and OPT(i) as follows:

SUM(i) = max(SUM(i - 1) + nums[i], nums[i])
OPT(i) = max(OPT(i - 1), SUM(i)).

Note: OPT is updated when a larger SUM[i] is discovered.

The initial values are SUM(0) = nums[0] and OPT(0) = nums[0]. We can do it in one pass. So here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
  int n = nums.length;
  int[] SUM = new int[n];
  int[] OPT = new int[n];
  SUM[0] = nums[0]; // init
  OPT[0] = nums[0];
  for (int i = 1; i < n; ++i) {
    SUM[i] = Math.max(SUM[i - 1] + nums[i], nums[i]);
    OPT[i] = Math.max(OPT[i - 1], SUM[i]);
  }
  return OPT[n - 1];
}

Since SUM(i) and OPT(i) could be calculated by the previous values, we don’t need arrays of size $n$ to store all information. Here is the code that reduces the space complexity:

1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
  int n = nums.length;
  int SUM = nums[0];
  int OPT = nums[0];
  for (int i = 1; i < n; ++i) {
    SUM = Math.max(SUM + nums[i], nums[i]);
    OPT = Math.max(OPT, SUM);
  }
  return OPT;
}

Time: $O(N)$
Space: $O(1)$