最大子序和問題【python兩種方式實作】

文章目錄

• • 問題描述：
  • 基于面向過程
  • • result:
  • 基于面向對象
  • • result:

問題描述：

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

例:

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

示例 2：

輸入：nums = [1]

輸出：1

示例 3：

輸入：nums = [0]

輸出：0

示例 4：

輸入：nums = [-1]

輸出：-1

示例 5：

輸入：nums = [-100000]

輸出：-100000

基于面向過程

nums = [-2,1,-3,4,-1,2,1,-5,4]
length = len(nums)
calculate_list = []
compare = []
sn=[]
for start in range(0, length):
    for end in range(0, length):
        calculate = nums[start:end + 1]
        if len(calculate) != 0:
            sn.append([start,end])
            result = sum(calculate)
            compare.append(result)
for snid,num in enumerate(compare):
    if num == max(compare):
        chilenumbers=nums[sn[snid][0]:sn[snid][1]+1]
print(compare)
print(f"連續子數組{chilenumbers}的和最大，為{max(compare)}。")
           

result:

[-2, -1, -4, 0, -1, 1, 2, -3, 1, 1, -2, 2, 1, 3, 4, -1, 3, -3, 1, 0, 2, 3, -2, 2, 4, 3, 5, 6, 1, 5, -1, 1, 2, -3, 1, 2, 3, -2, 2, 1, -4, 0, -5, -1, 4]
連續子數組[4, -1, 2, 1]的和最大，為6。
           

基于面向對象

class Solution(object):
    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)
            print(maxEndingHere, maxSofFar)
        return maxSofFar


# %%
s = Solution()
print(s.maxSubArray(nums=[4, -1, -8, -2, 9, 9, 7, 2, 4, -3]))
           

result:

1 1
-2 1
4 4
3 4
5 5
6 6
1 6
5 6
6