Skip to content

53. Maximum Subarray

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

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  var newSum = nums[0]
  var maxSum = nums[0]

  for (let i = 1; i < nums.length; i++) {
    newSum = Math.max(newSum + nums[i], nums[i])
    maxSum = Math.max(maxSum, newSum)
  }

  return maxSum
}
py
class Solution(object):

    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        newSum = maxSum = nums[0]
        for n in nums[1:]:
            newSum = max(newSum + n, n)
            maxSum = max(maxSum, newSum)
        return maxSum
go
func maxSubArray(nums []int) int {
    newSum := nums[0]
    maxSum := nums[0]
    for _, num := range nums[1:] {
        if newSum+num > num {
            newSum = newSum+num
        } else {
            newSum = num
        }
        if newSum > maxSum {
            maxSum = newSum
        }
    }
    return maxSum
}