53. Maximum Subarray

Source link: https://leetcode.com/problems/maximum-subarray/

Design

[-2,1,-3,4,-1,2,1,-5,4] → 6 ([4, -1, 2, 1])

Method I (Dynamic Programming)

  1. Observe the problem pattern and build the state transition function, which the current element will add previous accumulated values if they are larger than 0, otherwise add nothing but itself. So we could obtain the state transition function: f[i] = f[i - 1] > 0 ? nums[i] + f[i - 1] : 0
  2. Follow the pattern to build the state transition array and retrieve the maximum value within it.

Method II (Divide & Conquer)

This approach aims to improve the space complexity of Method I, as we can use a variable to record the maximum accumulated values so far.

  1. Initialize two variables, one for recording the final result and the other one tracking the larger one between the previous accumulated values and the current value.
  2. If the sum of values larger than the current result, update the final result.

Implementation

Method I (Dynamic Programming)

class Solution {
  public int maxSubArray(int[] nums) {
    int[] f = new int[nums.length];
    f[0] = nums[0];
    int max = nums[0];
    for (int i = 1; i < f.length; i++) {
      f[i] = nums[i] + (f[i - 1] > 0 ? f[i - 1] : 0);
      max = Math.max(f[i], max);
    }
    return max;
  }
}

Method II (Divide & Conquer)

class Solution {
  public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = nums[0];
    for (int i = 1; i < nums.length; i++) {
      sum = Math.max(sum + nums[i], nums[i]);
      if (sum > res) res = sum;
    }
    return res;
  }
}

Complexity Analysis

Method I (Dynamic Programming)

Time: $O(n)$

Space: $O(n)$

Method II (Divide & Conquer)

Time: $O(n)$

Space: $O(1)$