求数组中最大子数组的和01

　　要求：输入一个整型数组，数组里有整数也有负数；

　　　　　数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；

 　　　　 求所有子数组的和的最大值，要求时间复杂度为O(n)。

　　设计思想：这个题目重点就在解决求子数组的和，所以，自然而然的会想到求出所有子数组的和，然后比较大小，求出最大的子数组的和，但是通过编写代码发现，这样写下来的时间复杂度不是O（n），所以只能另换一种方法，由课堂上同学分享经验，我们想到，可以从数组的第一个元素开始依次求和，如果和为负数，再和之后的数相加只会让和变得越来越小，所以可以舍弃，同时定义的max变量中要保存到目前为止最大子数组的和。

　　具体代码如下：

//返回一个整数数组中最大子数组的和
//有正数、有负数、数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和、时间复杂度O(n)
//张哲、张晓菲 2016/3/22

#include<iostream>
using namespace std;

int main()
{
    int num,*arr;
    int sum=0;
    cout<<"请输入数组元素个数：";
    cin>>num;
    arr=new int[num];
    if(arr==NULL)
    {
        cout<<"申请空间失败！"<<endl;
        return 1;
    }
    cout<<"请输入数组元素的值：";
    for(int i=0;i<num;i++)
        cin>>arr[i];
    int max=arr[0];
    for(int j=0;j<num;j++)
    {
        if(sum<=0)
            sum=arr[j];
        else
            sum=sum+arr[j];
        if(sum>max)
            max=sum;
    }
    cout<<"子数组和的最大值为："<<max<<endl;
    delete [] arr;
    return 0;
}

运行结果如下：

　　总结：这次其实主要要解决的问题是如何让时间复杂度为O(n)，刚开始根本没有思路，因为能想出来的方法时间复杂度都不是O(n)，听其他同学分享的方法，感觉自己在编程上还和他人差一截，所以，要慢慢练，踏踏实实学。