Maximum Subarray – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Maximum Subarray – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object):
# def maxSubArray(self, nums):
# return self.maxSubArrayHelper(nums, 0, len(nums) - 1)
#
# def maxSubArrayHelper(self, nums, l, r):
# if l > r:
# return -2147483647
# mid = (l + r) / 2
# leftAns = self.maxSubArrayHelper(nums, l, mid - 1)
# rightAns = self.maxSubArrayHelper(nums, mid + 1, r)
# lMaxSum = res = 0
# for i in range(mid - 1, l -1, -1):
# res += nums[i]
# lMaxSum = max(res, lMaxSum)
# rMaxSum = res = 0
# for i in range(mid + 1, r + 1):
# res += nums[i]
# rMaxSum = max(res, rMaxSum)
# return max(lMaxSum + nums[mid] + rMaxSum, max(leftAns, rightAns))
# def maxSubArray(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# ls = len(nums)
# start = [0] * ls
# all = [0] * ls
# start[-1], all[-1] = nums[-1], nums[-1]
# for i in reversed(range(ls - 1)):
# start[i] = max(nums[i], nums[i] + start[i + 1])
# all[i] = max(start[i], all[i + 1])
# return all[0]
# def maxSubArray(self, nums):
# ls = len(nums)
# start, all = nums[-1], nums[-1]
# for i in reversed(range(ls - 1)):
# start = max(nums[i], nums[i] + start)
# all = max(start, all)
# return all
def maxSubArray(self, nums):
maxEndingHere = maxSofFar = nums[0]
for i in range(1, len(nums)):
maxEndingHere = max(maxEndingHere + nums[i], nums[i])
maxSofFar = max(maxEndingHere, maxSofFar)
return maxSofFar
