Python|贪心算法解最大子序和

vlambda
2020-05-10

Python|贪心算法解最大子序和

1 题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组[4,-1,2,1] 的和最大，为 6。

2 思路描述

第一时间想到的当然是暴力解决，基本思路就是遍历一遍，用两个变量，一个记录最大的和，一个记录当前的和。后面发现可以用贪心算法来解比较简单其基本思路是正在访问的节点值+此节点之前的最大值如果大于当前节点，则更新最大值为和，否则更新最大值为当前节点。

3 暴力解决的代码

nums=[-2,1,-3,4,-1,2,1,-5,4]
tmp = nums[0]
max_ = tmp
n = len(nums)
for i in range(1,n):
             # 当当前序列加上此时的元素的值大于tmp的值，说明最大序列和可能出现在后续序列中，记录此时的最大值
     if tmp + nums[i]>nums[i]:
         max_ = max(max_, tmp+nums[i])
         tmp = tmp + nums[i]
     else:
             #当tmp(当前和)小于下一个元素时，当前最长序列到此为止。以该元素为起点继续找最大子序列,
             # 并记录此时的最大值
         max_ = max(max_, tmp, tmp+nums[i], nums[i])
         tmp = nums[i]
print(max_)

4 贪心算法的代码

nums=[-2,1,-3,4,-1,2,1,-5,4]

lenth = len(nums)

cur_sum=max_sum = nums[0]

for i in range(1,lenth):

cur_sum = max(cur_sum+nums[i], nums[i])

max_sum = max(cur_sum, max_sum)

print(max_sum)

5 总结

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

END

编辑 | 王楠岚

责编 | 王自强

where2go 团队

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！

vlambda博客
学习文章列表