求最大连续子序列和的 N 种方法

max_cont_subseq.md

求最大连续子序列和的 N 中方法

1) O(n^3)

def max_continuous_subsequence(l):
    maxsofar = 0
    length = len(l)
    for i in range(length):
        for j in range(i, length):
            sum = 0
            for k in range(i, j+1):
                sum += l[k]
            maxsofar = max(maxsofar, sum)
    return maxsofar

2) O(n^2)

def max_continuous_subsequence(l):
    maxsofar = 0
    length = len(l)
    for i in range(length):
        sum = 0
        for j in range(i, length):
            sum += l[j]
            maxsofar = max(maxsofar, sum)
    return maxsofar

3) O(nlogn)

分治法 将数组分为两部分 a b，最大的子序列和一定为 a 中最大子序列和，或 b 中最大子序列和，或包含边界的最大子序列和

def max_continuous_subsequence(l, begin, end):
    if begin > end:
        return 0
    if begin == end:
        return max(0, l[begin])
    mid = (begin + end) / 2
    # 从分界处向左寻找
    lmax = sum = 0
    for i in range(mid, 0, -1):
        sum += l[i]
        lmax = max(lmax, sum)
    # 从分界处向左寻找
    rmax = sum = 0
    for i in range(mid+1, end+1):
        sum += l[i]
        rmax = max(rmax, sum)
    return max(lmax+rmax, max_continuous_subsequence(l, begin, mid),
               max_continuous_subsequence(l, mid+1, end))

4) O(n)

def max_continuous_subsequence(l):
    maxsofar = 0
    sum = 0
    for i in range(len(l)):
        sum = max(sum + l[i], 0)
        maxsofar = max(maxsofar, sum)
    return maxsofar