[数据结构与算法]Python - 最大连续子序列和

Python - 最大连续子序列和

最常考的面试题了。

代码

输出最大值

动态规划

# -*- coding: utf-8 -*-
# @File : test.py
# @Author : xianglun918
# @Time : 2021/09/17 12:56:15

# 处理输入
nums =  [int(i) for i in input().split()]

# 如果没有输入 - 输出 -1 （其实理论上最少应该有一个输入）
if not nums:
	print(-1)
else:
	# 动态规划
	# nums[i] 的值是 nums[i] 或者 前面最大子序列的和 + nums[i]
	# 这样保证了如果前面的序列和是负数，就重新开始计数
	# 保证了每一段序列和是单向增长的 (最多从 i 开始重新增长）
	for i in range(1, len(nums)):
	    nums[i] = max(nums[i], nums[i] + nums[i-1])
	
	print(max(nums))

当然这样只能找到最大连续子序列的和，不能输出最大连续子序列。

我们加两个 index 记录，用来输出最大连续子数组。

nums =  [int(i) for i in input().split()]
ref = nums.copy()

# sum up all numbers
idx1, idx2 = 0, 0
max_ = nums[0]

for i in range(1, len(nums)):
    if nums[i] > nums[i] + nums[i-1]:
        if nums[i] > max_:
            max_ = nums[i]
            idx1, idx2 = i, i
    else:
        nums[i] = nums[i] + nums[i-1]
        if nums[i] > max_:
            max_ = nums[i]
            idx2 = i

ans = [str(i) for i in ref[idx1:idx2+1]]
print(' '.join(ans))