问题：一个由正数、负数、0组成的序列中，求一个连续子序列，使他们之和最大

 

解一：暴力法，直接求出所有可能，找出最大值

1 MAX_SEQ_SUM( A, len ) 2     max = A[0] 3     max_b = max_e = 0 4  5     for i -> 0:len-1 6         sum = 0 7         for j->i:len-1 8             if j == i then sum = A[i] 9             else sum += A[i]10             if sum > max then11                 max = sum12                 max_b = i13                 max_e = j14     15     return max,max_b,max_e

复杂度为：O(n^2)

 

解法2：遍历数组时记录当前和，如果和大于最大值，则记录，如果和小于0，则从当前元素重新计算

MAX_SEQ_SUM(A,len)    sum = max = A[0]    max_b = max_e = 0    for i -> 1:len        if sum < 0 then sum = A[i] ; b = e = i;        else  sum += A[i] ; e = i;        if sum < max then  max = sum ; max_b = b; max_e = e;    return max,max_b,max_e

复杂度为：O(n)