最大子序和问题【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