Problem

53. Maximum Subarray

Greedy

Local optimal solution will lead to global optimal solution.

For each element, we need to determine whether to discard current sum and restart a new sum from the current element, or to continue with the current sum and add the current element to it.

• If current sum < 0, adding the current element will make the current element(potential new sum) smaller, which is not optimal.
• If current sum > 0, adding the current element will make current element bigger.
• Restart or not, we compare the current sum with a stored maximum value to determine the optimal solution.

Pseudo Code

maxSubArray(A)
  N = A.length
  max = A[1]
  currSum = A[1]

  for i = 2 to N
    if currSum > 0
      currSum += A[i]
    else
      currSum = A[i]

    if currSum > max
      max = currSum

  return max;

Complexity

Time - O(N). Just one interation. Space - O(1). No extra space needed.

Dynamic Programming

• maxium sum - the sum starts from some element on the left and ends with the current element
• current element - A[i]
• maximum sum of previous element - dp[i - 1]
• maximum sum of current element - dp[i]

We calculate maximum sum for each element in the original array A. Let dp[i] represent the maximum sum at i index

1. Base Cases.
   • When there is only one element, the maximum sum is the element itself. dp[1] = A[1]
2. Transition Function.
   • If the previous maximum is greater than 0, the current maximum sum is the sum of the previous maximum and the current element. dp[i] = dp[i - 1] + A[i]
   • Else, the current maximum sum is the current element itself. dp[i] = A[i]
3. While calculating each maximum sum, we can update global maximum sum.

Pseudo Code

maxSubArray(A)
  N = A.length
  Define dp[1...N]
  dp[1] = A[1]
  maxSum = dp[1]
  for i = 2 to N
    if dp[i - 1] > 0
      dp[i] = dp[i - 1] + A[i]
    else
      dp[i] = A[i]
    maxSum = max(maxSum, dp[i])
  return maxSum

If allowed, we can directly change the original array in place, rather than using an extra array to hold the maximum sums.

Optimized space

maxSubArray(A)
  N = A.length
  maxSum = A[1]
  for i = 2 to N
    if A[i - 1] > 0
      A[i] += A[i - 1]
    maxSum = max(maxSum, A[i])
  return maxSum

Divide and Conquer

Introduction To Algorithm - Chapter 4 Divide-and-Conquer

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the problem in a straightforward manner.
3. Combine the solutions to the subproblems into the solution for the original problem.

• What is the base case? There is only one element in each half respectively. We can easily determine the largest range by comparing the left half, the right half and the sum of the whole.

• How to solve the case? Once the base case is resolved, we can combine the solutions of base cases and build solution for the case of a larger size. The solution of a subproblem comprise a max sum on the left, a max sum cross the left and the right (starting some element in the left half, and ending some element in the right half), and a max sum on the right.

maxCrossSum(A, left, middle, right)
  if left == right
    return A[left]
  leftMax = Integer.MIN
  temp = 0
  for i = middle to left
    temp += A[i]
    if temp > leftMax
      leftMax = temp
      leftBoundary = i
  rightMax = Integer.MIN
  temp = 0
  for i = middle + 1 to right
    temp += A[i]
    if temp > rightMax
      rightMax = temp
      rightBoundary = i
  return (leftBoundary, rightBoundary, leftMax + rightMax)