题目描述: 给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个非连续子序列,使其和最大,输出最大子序列的和。 这里非连续子序列的定义是,子序列中任意相邻的两个数在原序列里都不相邻。 例如,对于L=[2,-3,3,50], 输出52(分析:很明显,该列表最大非连续子序列为[2,50]).
示例:
输入: L = [2, -3, 3, 50] 输出:52
分析: 上一题我们求了最大连续子序列的和,这一题是求最大非连续子序列的和。对于我们的这个问题,我们来稍微的小分析一下。
我们首先定义数组 L[k]
表示第 k 个位置的最大非连续子序列和。
那么我们要确定第 L[k+1]
个位置的最大和,应该就是与前 L[k-1]
个中最大的和相加就可以了。
非连续嘛,就是不考虑第 L[k]
个位置,因为如果考虑了第 L[k]
个时,第 L[k+1]
个就有可能和第 L[k]
个连在一起,变成连续的子序列。
代码:
1
2
3
4
5
L = [0] + L
for i, value in enumerate(L):
if i > 1:
L[i] = L[i] + max(L[:i-1])
print(max(L))