python leetcode53:最大子數組求和

題目：

"""
給定一個整數數組 nums ，
找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。
"""

法1：暴力求解（超出時間限制）

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)

法2：貪心算法之雙重比較

 若當前元素之前之和小於0，則丟棄當前元素之數列。

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]) #比較當前值和sum
max_sum = max(cur_sum,max_sum) #比較歷史最大值和當前最大值
return max_sum
nums = [-2,1,-3,4,-1,2,1,-5,4]
S = Solution()
result = S.maxSubArray(nums)
print(result)

法3：動態規劃法

若前一個元素大於0，則加在當前元素上。

# 1.雙重比較
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 #所指元素sum
max_sum = max(pre_sum,max_sum) #比較最大值
else:
pre_sum = nums[i]
max_sum = max(pre_sum, max_sum)
return max_sum
#2.列出所有滿足條件的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 #所指元素sum
lst.append(pre_sum)
else:
pre_sum = nums[i]
lst.append(pre_sum)
return max(lst) #取列表中最大值
#3.用sum替換原位置的值
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] #用sum替換原位置的值
return max(nums) #取列表中最大值