Python leetcode53: maximum subarray sum

subject ：

"""
Given an array of integers nums ,
Find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .
"""

Law 1： Violent solution （ Time limit exceeded ）

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
lst = []
for i in range(len(nums)):
sum = 0
for j in range(i,len(nums)):
sum += nums[j]
lst.append(sum)
return max(lst)

Law 2： The double comparison of greedy algorithm

  If the sum before the current element is less than 0, Then discard the current element sequence .

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur_sum = max_sum = nums[0]
for i in range(1,len(nums)):
cur_sum = max(nums[i],cur_sum+nums[i]) # Compare current value with sum
max_sum = max(cur_sum,max_sum) # Compare the historical maximum with the current maximum
return max_sum
nums = [-2,1,-3,4,-1,2,1,-5,4]
S = Solution()
result = S.maxSubArray(nums)
print(result)

Law 3： Dynamic programming

If the previous element is greater than 0, Is added to the current element .

# 1. Double comparison
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre_sum = max_sum = nums[0]
for i in range(1,len(nums)):
if pre_sum > 0:
pre_sum = nums[i] + pre_sum # Reference element sum
max_sum = max(pre_sum,max_sum) # Compare Max
else:
pre_sum = nums[i]
max_sum = max(pre_sum, max_sum)
return max_sum
#2. List all that meet the conditions sum
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
pre_sum = 0
lst = []
for i in range(0,len(nums)):
if pre_sum > 0:
pre_sum = nums[i] + pre_sum # Reference element sum
lst.append(pre_sum)
else:
pre_sum = nums[i]
lst.append(pre_sum)
return max(lst) # Take the maximum value in the list
#3. use sum Replace the value of the original position
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
if nums[i-1] > 0:
nums[i] += nums[i-1] # use sum Replace the value of the original position
return max(nums) # Take the maximum value in the list