Skip to main content

53. Maximum Subarray

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

Python​

First Try​

Timeout, O(nlogn)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans_sum = 0
        for start in range(0, len(nums)):
            for end in range(start, len(nums)+1):
                if (current_sum := sum(nums[start:end])) > ans_sum:
                    ans_sum = current_sum
        return ans_sum

O(n) Solution​

O(n) Solution, which don't care the ans array but only reach the sum()

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans_sum = None
        current_sum = -10^4
        for num in nums:
            current_sum = max(current_sum + num, num)
            ans_sum = current_sum if ans_sum is None else max(ans_sum, current_sum)
        return ans_sum

### O(n) clear solution​

from math import inf


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        total = -inf
        max_total = -inf
        for num in nums:
            total = max(total+num, num)
            max_total = max(max_total, total)
        return max_total

Bottom-Up DP​

Same as previous solution, but follow the DP pattern

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * (len(nums)+1)

        ans = nums[0]
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] = nums[i] + nums[i-1]
                ans = max(ans, nums[i])

        return ans

Go​

func maxSubArray(nums []int) int {
    var total int = -10000
    var max_total int = -10000

    for _, num := range nums {
        if num > total + num {
            total = num
        } else {
            total += num
        }

        if (max_total < total) {
            max_total = total
        }
    }

    return max_total
}

JS​

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let max = -Infinity;
    let cur = 0;

    for (let num of nums) {
        if (cur + num < num) {
            cur = num;
        } else {
            cur += num;
        }
        max = Math.max(cur, max);
    }

    return max;
};

/**
 * max -2  1  1  4  4  5  6  6  6
 *
 * cur -2  1 -2  4  3  5  6  1  5
 * num -2  1 -3  4 -1  2  1 -5  4
 *.        *    *
 *  1 > (-2 + 1) -> max: 1, cur: 1
 *  4 > (-2 + 4) -> max: 4, cur: 4
 */