Skip to content

53.maximum-subarray.md

Latest commit

 

History

History
284 lines (224 loc) · 8.43 KB

53.maximum-subarray.md

File metadata and controls

284 lines (224 loc) · 8.43 KB

53. Maximum Subarray

Brute Force (TLE)

fun maxSubArray(nums: IntArray): Int {
    var max = Int.MIN_VALUE
    for (i in 0 until nums.size) {
        for (j in i until nums.size) {
            var sum = 0
            for (k in i..j) {
                sum += nums[k]
            }
            if (sum > max) {
                max = sum
            }
        }
    }
    return max
}
  • Time Complexity: O(n^3).
  • Space Complexity: O(1).

Dynamic Programming

From brute force, we can see that the sum of subarrays is calculated repeatedly. we can use dynamic programming to store the results of subproblems and avoid redundant calculations.

At each index, the maximum subarray ending at index i, we have two choices:

  • Can I extend the previous one? previousMax + nums[i].
  • Start fresh at nums[i]?

Let dp[i] represent the maximum subarray sum ending at i, then the state transition can be defined as dp[i] = max(dp[i - 1] + nums[i], nums[i]). And more important, dp[i] is the maximum result ending at index i, which is NOT the global maximum (see the example below). So we need to keep track of the global maximum among all possible subarray ends.

Examples

       [-2, 3, -1]
dp[i]   -2  1   0   // dp[n - 1] = 0, it's not the global maximum
maxSum  -2  3   3   // We should keep track of the global maximum

       [5, -100, 1]
dp[i]   5  -95  -94
maxSum  5   5    5

Pitfalls

There are two pitfalls:

  1. Size of the array is 1, we need to return nums.first(). Or we can initialize our answer with nums.first() at the beginning.
  2. We need to keep track of the global maximum, not just the local maximum, not return dp[n - 1]. Please remember the definition of dp[i] is the maximum subarray sum ending at i, not the global maximum. (See the example above, dp[n - 1] is not always the global maximum)

SRT-BOT

  • Subproblem: f(i) is the maximum subarray ending at i (but not global maximum).
  • Relation: f(i) = max(f(i - 1) + A[i], A[i]).
  • Topological sort: Increasing order of i.
  • Base case: f(0) = A[0].
  • Original problem: max(f(i)) for all i.
  • Time complexity: O(n).

Top-down DP

2, -1, 3

f(2, -1, 3) = 4
    max(f(2, -1) + 3, 3)

    f(2, -1) = 1
        max(f(2) - 1, -1) = max(1, -1)

            f(2) = 2
                max(f(_) + 2, 2)
fun maxSubArray(nums: IntArray): Int {
    topDown(nums, nums.size - 1)
    return result
}

private val memo = hashMapOf<Int, Int>()
private var result = Int.MIN_VALUE

private fun topDown(nums: IntArray, i: Int): Int {
    if (i < 0) return 0
    if (!memo.containsKey(i)) {
        val currentMax = maxOf(nums[i], topDown(nums, i - 1) + nums[i])
        // Update the global maximum
        result = maxOf(currentMax, result)
        memo[i] = currentMax
    }
    // Return the local maximum
    return memo[i]!!
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

Dynamic Programming (Kadane's Algorithm)

fun maxSubArray(nums: IntArray): Int {
    if (nums.isEmpty()) return 0
    val dp = IntArray(nums.size)
    dp[0] = nums.first()
    var maxSum = nums.first()
    for (i in 1 until nums.size) {
        // We keep appending the i-th number or restart a totally new number.
        dp[i] = maxOf(dp[i - 1] + nums[i], nums[i])
        maxSum = maxOf(maxSum, dp[i])
    }
    return maxSum
}
  • Time Complexity: O(n).
  • Space Complexity: O(n).

With space optimization:

fun maxSubArray(nums: IntArray): Int {
    if (nums.isEmpty()) return 0
    var globalMax = nums.first()
    var previous = nums.first()
    for (i in 1 until nums.size) {
        val current = max(previous + nums[i], nums[i])
        globalMax = max(globalMax, current)
        previous = current
    }
    return globalMax
}
  • Time Complexity: O(n).
  • Space Complexity: O(1).

References

Prefix Sum (Naive)

subarraySum(i, j) = prefixSum[j] - prefixSum[i - 1] if i > 0
subarraySum(i, j) = prefixSum[j]                    if i == 0

We can calculate the prefix sum for each index, and then use two nested loops to calculate the subarray sum for each pair of i and j.

    A, B, C, D
 i
    j  j  j  j = A, A + B, A + B + C, A + B + C + D
    i
       j  j  j = B, B + C, B + C + D
       i
          j  j = C, C + D
          i
             j = D
fun maxSubArray(nums: IntArray): Int {
    if (nums.isEmpty()) return 0
    val n = nums.size
    val prefixSum = IntArray(n)
    prefixSum[0] = nums.first()
    var ans = nums.first()
    for (i in 1 until n) {
        prefixSum[i] = nums[i] + prefixSum[i - 1]
        ans = maxOf(ans, prefixSum[i]) // prefixSum[i] is the subarray sum of nums[0..i], it's when i == 0
    }
    for (i in 0 until n) {
        for (j in i + 1 until n) {
            ans = maxOf(ans, prefixSum[j] - prefixSum[i])
        }
    }
    return ans
}
  • Time Complexity: O(n^2).
  • Space Complexity: O(n) for the prefix sum array.

Prefix Sum (Enumeration)

Let's define:

  • prefixSum[i]: sum of subarray nums[0..i].
  • The sum of subarray nums[i..j] is prefixSum[j] - prefixSum[i - 1].

To maximize sum(nums[i..j]), we need to find the minimum prefix sum before j, that is to minimize prefixSum[i - 1]. To minimize prefixSum[i - 1], we can keep track of the minimum prefix sum seen so far.

We can enumerate nums[j], keep track of the minimum prefix sum seen so far, and calculate the maximum subarray sum prefixSum[j] - minPrefixSum.

Let's walk through the array [-2, 3, -1]:

prefixSum   0  -2  1   0
pre - min      -2  3   2
   maxSum -oo  -2  3   3
minPrefix   0  -2 -2  -2

Another example [5, -100, 1]:

i num prefixSum minPrefix prefixSum - minPrefix maxSum
- - 0 0 - -oo
0 5 5 0 5 - 0 = 5 5
1 -100 -95 0 -95 - 0 = -95 5
2 1 -94 -95 -94 - (-95) = 1 5 
fun maxSubArray(nums: IntArray): Int {
    var minPrefixSum = 0 // Wee need `0` as the base prefix sum. Not `nums.first()` or `Int.MIN_VALUE` (see the explanation below)
    var prefixSum = 0
    var maxSum = Int.MIN_VALUE // Or it's OK to start with `nums.first()`

    // We always iterate from 0 to n - 1.
    for (num in nums) {
        prefixSum += num
        maxSum = maxOf(maxSum, prefixSum - minPrefixSum)
        minPrefixSum = minOf(minPrefixSum, prefixSum)
    }
    return maxSum
}

Why we need 0 as the base prefix sum? Not nums.first() or Int.MIN_VALUE?

In prefix sum problem, we often need to calculate subarraySum(i, j) = prefixSum[j] - prefixSum[i - 1]. To correctly compute the subarray sum that starts at index 0, you must treat the prefix sum before the first element as 0. This ensures that you capture the full range of subarrays, especially when the subarray starts at the beginning of the array.

Let's take an example: [1, -3, 2]:

pre[i] = sum of subarray nums[0..i]
nums = [1, -3, 2]
pre =  [1, -2, 0]

We want to calculate subarraySum(0, 2) what is pre[2] - pre[-1] = -2 - 0 = -2. For pre[-1] which does not exist, we need to treat it as 0 by convention.

WA

It starts prefixSum with nums.first(), but the loop skips index 0.

// Failed at : [-2,1], expected 1, got -1
fun maxSubArray(nums: IntArray): Int {
    var minPrefixSum = 0            // 0
    var prefixSum = nums.first()    // -2
    var maxSum = nums.first()       // -2

    for (i in 1 until nums.size) {
        prefixSum += nums[i] // -1
        maxSum = maxOf(maxSum, prefixSum - minPrefixSum)    // -1 - 0 = -1, WA, it should be -1 -(-2) = 1
        minPrefixSum = minOf(minPrefixSum, prefixSum)       // -1, it should be -2
    }
    return maxSum
}

// Failed at: [5,4,-1,7,8], expected 23, got 18 (4, -1, 7, 8)
fun maxSubArray(nums: IntArray): Int {
    var minPrefixSum = nums.first()
    var prefixSum = nums.first()
    var maxSum = nums.first()

    for (i in 1 until nums.size) {
        prefixSum += nums[i]
        maxSum = maxOf(maxSum, prefixSum - minPrefixSum)
        minPrefixSum = minOf(minPrefixSum, prefixSum)
    }
    return maxSum
}