最大连续子序列 #

1. 最大连续子序列问题的介绍
2. 最大连续子序列的算法分析
3. 最大连续子序列的代码实现

最大连续子序列问题的介绍 #

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），并且返回其最大和。例如: 给定序列[-2, 11, -4, 13, -5, -2]，其最大连续子序列为[11, -4, 13]，最大和为20。

最大连续子序列的算法分析 #

贪心求解最大连续子序列的和时：解局部最优解: 以 a[i] 结尾的子序列和最大的 s[i];全局最优解: 在 s[i] 中找最大的即是全局最优解，算法步骤如下:
1)找到以 a[i] 结尾的连续非空子序列中和最大 s[i]
2)如果这个序列 s[i] 为负数，那么以 a[i] 结尾的连续非空子序列中和最大的序列就是 a[i] 本身,如果这个序列 s[i] 为正数，那么以 a[i] 结尾的连续非空子序列中和最大的序列就是 a[i]+s[i]
3)在所有的 s[i] 中找最大的，即 max(s[i])

最大连续子序列的代码实现 #

a=[int(i) for i in input().split()]
nowsum=0#当前以a[i]结尾的最大子序列和即s[i]
maxsum=0
for i in range(len(a)):
    nowsum=nowsum+a[i]#a[0]是以a[0]为结尾的最大子序列和
    if nowsum> maxsum:
        maxsum=nowsum
    if nowsum< 0:#如果这个和小于零，则以a[i+1]为结尾的最大子序列和就是它本身
        nowsum=0
print(maxsum)

小结 #

• 根据最大连续子序列问题，理解贪心算法
• 掌握最大连续子序列求解的贪心算法，能够根据实际问题作出合适的贪心策略

习题 #

1. 使用回溯法,求解最大连续子序列问题，对比使用贪心算法的区别