时间复杂度为n的求最大子数组的方法

题目：时间复杂度为n的求最大子数组 

成员：马国彬，李小超

这道题相对来说比较简单，我和我的搭档李小超在上课时很快就完成了，主要是用了两层for循环进行比较，但是跟老师交流之后，老师对我们的时间复杂的提出了要求，我们的时间复杂度为n方，而不是n，下课之后，我和李小超经过一晚上的思考，想出了解决的方案，我们两个人各想出了一个程序，大体思路差不多，这里给上我的程序并做分析。

// 最大数组2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

int main(int argc, char* argv[])
{
    int a[5]={7,87,-14,15,7};
    int i;
    int max=a[4];
    for(i=0;i<4;i++)
    {
        if(a[i]>max)
            max=a[i];
    }
    for(i=4;i>0;i--)
    {
        if(a[i]>0)
        {

            a[i-1]=a[i-1]+a[i];
            if(max<a[i-1])
                max=a[i-1];
            if(a[i-1]<=0)
            {
                i--;
                if(max<a[i-1]
                  max=a[i-1];
            }
        }
    }

    printf("%d",max);
    return 0;
}

首先将数组的最后一个数赋给max，然后将max与每一个数进行比较，如果比数组小， 则交换。然后通过一个for循环，开始查找最大字数组。我是从数组组后一个开始倒着逼得，首先看当前数组也就是最后一个是否大于0，如果大于，就给前一个数加上当前数。再与max比较。若大于max则交换。然后将前一个数与0比较，如果小于0，说明这两个数相加较小，是个负值，这样就将这两个数舍去，因为是负的，只会使和更小。因为之前已经给前一个数加上了当前的数了，为了使这两个数都能舍去，给一个i--,这样，当for循环执行了一次之后，又给了一个i--，这样就跳了两次，把之前的两个要舍去的数都跳过去了。同时，为了使max准确表示当前最大字数组的和，在i--之后，加一个max=a[i-1];

通过几次循环之后，就能得到最大的max，同时，这也是线性的，时间复杂度较低。