数组连续子序列的最大的和-四种算法，四种时间复杂度

给定一组数据：31, -41, 59, 26, -53, 58, 97, -93, -23, 84。要求找到这组数据中连和最大的子序列，相信很多人都看过这个算法，能够直接给出线性时间复杂度的解法。但是还是有其他解法的，而且是循序渐进的，从O(n^3), O(n^2), O(n*logn)到O(n)。

在开始算法之前要进行一下约定，如果当前输入的都是负数的时候，综合最大的子序列是空的，总和为0.

第一种方法就是brute-force解法，就是对满足所有的0<=i < j < n的组合(i,j)进行迭代，对于每个整数对都要计算a[i,j]的总和，这个算法有个特点，也就是造成时间复杂度很高的缺点，对于每次计算的结果没有记录，只是简单的将此次计算的结果和上次计算的结果进行比较，求得当前最大值后，就给扔掉了。下面给出算法：

#include<stdio.h>int get_max2(int *a, int n) {int current_max = a[0];int final_max = a[0];int i;for(i = 1; i < n; i++) {if(current_max + a[i] > 0) {current_max += a[i];} else {current_max = 0;}if(current_max > final_max) {final_max = current_max;}}return final_max;}void main() {int a[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};int n = sizeof(a) / sizeof(int);int rst = get_max2(a, n);printf("max_sum = %d\n", rst);}