连续子数组之和最大

问题:求整型数组的连续子数组之和的最大值，且时间复杂度不超过O(n)。

一 设计思路:当遍历所有的子数组之和求最大值时，时间复杂度显然是O(n^2),所以需要用一种简便的方法来解决问题。假设连续子数组为A[I]-A[J],考虑从第一个数A[0]开始，如果0=i=j，那么a[0]本身就是最大值，如果0=i<j,那么a[0]是最大子数组的开头，如果0<i<j,那么a[0]不在最大子数组中。综上所述，可以将n个数组的问题化为n-1个。故设置两个变量分别设为连续子数组之和sum和最大值max，将他们初始化为a[0]，sum与下一个数即a[1]相加，判断如果大于这个数则将和赋给sum,否则将这个数赋值给sum。最后判断sum与max的大小，将最大值赋给max，这个判断条件必须在循环之内，因为连续的相加过程中会使sum变小，到最后sum可能不是原来的那个最大值。

二 代码实现:

#include<iostream>
using namespace std;

void main()
{
   int i,n,a[1000];
   cout<<"请输入数组长度:";
   cin>>n;
   for(i=0;i<n;i++)
   {
       a[i]=rand()%90-40;
   }
   for(i=0;i<n;i++)
   cout<<a[i]<<" ";
   cout<<endl;
   int max=a[0],sum=a[0];
   for(i=1;i<n;i++)
   {
        if(sum+a[i]>a[i])
        { 
              sum=sum+a[i];
        }
        else sum=a[i];
   }

   if(max<sum)
   {
        max=sum;
   }

        cout<<"最大子数组之和为"<<max<<endl;
}

 三 截图:

四 总结:主要问题是如何使代码的时间复杂度不超过O(n)，但是自己怎么做，时间复杂度还是O(n^2),所以我查询了网上的代码。其中csdn上的一位网友的动态规划，分而治之的思想很是让我受启发。这种思想的关键在于如何将一个问题化大为小，从最基本的问题出发解决实际问题。自己的实力还有待提高。

五 

时间记录日志表

日期	开始时间	结束时间	中断时间	净时间	活动	备注
3/20	21:20	21:40		20	思考设计思路
3/21	8:30	9:40	10	60	编程	设计整型数组
	3:20	4:10	15	35	查阅资料	使时间复杂度不超范围
3/22	19:10	19:50		40	编程	利用动态规划思想
3/23	10:10	11:00		50	整理总结

周活动总结表

日期/任务	听课	编程	阅读课本	课外活动	日总结
周日		40	60	120	220
周一	200	60	30	60	350
周二	400	100	35		535
周三	100	60		50	210
周四	300	46	25		371
周五	300	50	30	40	420
周六		95	50	120	265
周总结	1300	451	230	390	2371

缺陷记录日志

日期	编号	类型	引入阶段	排除阶段	修复时间	修复缺陷
3/21	1	20	编码	编译	1min
	缺少分号";"
3/22	2	20	设计	编译	1min
	数组数值都为正数
3/22	3		编码	编译	5min
	判断最大子数组之和在循环之外,结果出错