问题

给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个连续子序列，使其和最大，输出最大子序列的和。 例如，对于L=[2,-3,3,50]， 输出53

方法一：暴力破解
最简单的方法就是直接求解出所有的子序列之和，然后比较子序列之和，求出最大值。那么如何求解子序列呢？首先子序列的起始位置可能是任意的，结束位置也可以是任意的。可以一层循环确定子序列的起始位置，嵌套一层循环确定子序列的结束位置并求和，（这里我简化了，直接利用上一个子序列的结果进一步求和），添加到空列表中。

sums = 0
L_fy = []
for i in range(len(L)):
	for j in range(i, len(L))：
		sums += L[j]
        L_fy.append(sums)
    sums = 0
maxs = max(L_fy)
return maxs123456789

改进一
这肯定是最基本的方法了，看看还能不能改进呢？一个改进的方法，就是在比较的时候，不用先存到列表里。计算出一个子序列和就与之前的最大值比较，得出当前的最大值。

maxs = L[0]   #最好不要设为0，因为下面比较的时候，如果全是负数，那最终就为0，明显是不对的。 
sums = 0
for i in range(len(L)):
    for j in range(i, len(L)):
        sums += L[j]
        if maxs < sums:
            maxs = sums
    sums = 0
return maxs123456789

改进二
参考了其他博客的方法，可以用分治法来做。这样想，最大子序列和要么在左半部分，要么在右半部分，要么横跨左右两部分。所以分别求出这三种情况的最大序列和，比较求得最终的最大子序列和。左半部分和右半部分可以用递归求，那么只需要在函数中求解横跨两部分的最大子序列即可。从中间值开始，向前面两种方法那样，起始位置为中间下标，一部分向左求和，另一部分向右求和，最终两部分相加即可。因为在Python中组合数据类型可以不用声明全局，直接是地址传值，所以直接用了。

def solve_it(l, r):
    if l > r:
        return 0
    elif l == r:
        return L[l]
    else:
        mid = (l + r) // 2
    lmax = L[mid]     # 最好不设为0，因为下面比较的时候，如果是整个列表全是负数就不适合了，最终结果就为0。
    lsum = 0
    for i in range(mid,l-1,-1):
        lsum += L[i]
        if lmax < lsum:
            lmax = lsum
    
    rmax = L[mid+1]
    rsum = 0
    for j in range(mid+1, r+1):
        rsum += L[j]
        if rmax < rsum:
            rmax = rsum

    Mmax = lmax + rmax
    Lmax = solve_it(l,mid)
    Rmax = solve_it(mid+1,r)

    result = max(Mmax, Lmax, Rmax)
    return result
 print(solve_it(0, len(L)-1))12345678910111213141516171819202122232425262728

改进三
这里还是借鉴的其他博客的，属于动态规划法。也可以换种思路想，当前的最大子序列和一定是由之前的最大子序列和加上（或不考虑）当前元素构成的。那么我们从第一个元素开始，假设第一个元素为目前的最大子序列和，下一个最大子序列一定是这个子序列加上第二个元素或者丢掉第一个元素。那么何时加上第二个元素呢？只要第一个元素不为负数（因为负数只会越加越小，根本不会构成最大子序列和），那么就是第一个子序列和加上这个元素。如果是负数，那么目前最大的子序列的起始位置只能是这个元素。这样每次循环都得到目前最优的子序列，知道循环结束。
回归到第一种方法，每次循环都是起始位置的确定的，结束位置也是在循环不断变化中。此方法是在每次循环中起始位置（可能）和结束位置都在变化。

def solve_it():
    maxsum = L[0]
    maxhere = L[0]
    for i in range(1,len(L)):
    	# 判断起始位置应不应该改变，并根据U结束位置求解当前的子序列和
        if maxhere <= 0:
            maxhere = L[i]
        else:
            maxhere += L[i]
        # 判断是否是最大子序列和
        if maxsum < maxhere:
            maxsum = maxhere
    return maxsum

print(solve_it())

作者：qq_42907161

链接：https://blog.csdn.net/qq_42907161/article/details/107690007

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。