1、题目要求：
（1）输入一个整形数组，数组里有正数也有负数；
（2）数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；
（3）求所有字数组的和的最大值，要求时间复杂度为O（n）。
2、实现思路：
（1）先要输入一组整形数，直到输入回车结束；
（2）分离出每一个数，按顺序存放到整形数组里；
（3）每一个、相连续两个、三个……都是子数组，分别求出子数组的和，把最大的和输出。
3、思路整理（实现步骤）：
（1）输入数组元素，用空格分开，输入的是字符，转化为整形数，连续的0~9字符，按所在数位进行放大求和，得出输入的整形数；
（2）若输入的字符是空格，则将空格前的数存放入整形数组中；
（3）按回车，输入结束，开始计算；
（4）计算过程：
从第一个数开始，依次比较大小，最大的数单独存放在num1；
第一个数，开始，求arr[1]+arr[2]+……+arr[n]，将所有和的最大值与num1 比较，最大值存入num1；
再求arr[i]+arr[i+1]+……+arr[k]，将所有和的最大值与num1 比较，最大值存入num1；
直到arr[i] 为最后一个数为止，num1 即为子数组最大的和。
4、源代码：
#include <iostream> #include <string> #include<ctime> #include<cmath> #define N 10 using namespace std; char arr[1000]; string str; int arr1[100]; int k=0; void chtoin() { int i=0; int j=10; int num1=0; int num2=0; bool flag=0; char ch[]="#"; cout<<"请输入数组（中间以空格隔开）："<<endl; gets(arr); strcat(arr,ch); for (;;) { if(arr[i]=='#') { if (flag==0) { arr1[k]=num2; k++; } else { arr1[k]=0-num2; k++; } break; } else { if (arr[i]==' ') { if (flag==0) { i++; arr1[k]=num2; num2=0; k++; } else { i++; arr1[k]=0-num2; num2=0; flag=0; k++; } } else if (arr[i]=='-') { i++; flag=1; } else { num1=arr[i]-'0'; num2=num1+num2*j; i++; } } } } void main() { int j=0; int i=0; chtoin(); int num1=arr1[0],num2=0; for(;;) { num2+=arr1[i]; if (num2>num1) { num1=num2; } if (j==N) { break; } else { if (i==N-1) { num2=0; j++; i=j-1; } } i++; } cout<<num1<<endl; }
5、运行结果
23-4+5+7-3+6=34
5+7-5+34=41
项目计划日志（单位：h）：
| 听课 | 编写程序 | 阅读相关书籍 | 网上查找资料 | 日总计 | |
| 周一 | 2 | 0 | 1 | 0.5 | 3.5 |
| 周二 | 0 | 1 | 0.5 | 0 | 1.5 |
| 周三 | 0 | 2 | 0 | 0 | 2 |
| 周四 | 2 | 1.5 | 0 | 1.5 | 5 |
| 周五 | 0 | 2 | 0.5 | 0 | 2.5 |
| 周六 | 0 | 3 | 0 | 0 | 3 |
| 周日 | |||||
| 周总计 | 4 | 9.5 | 2 | 2 | 17.5 |
时间记录日志（单位：min）：
| 日期 | 开始时间 | 结束时间 | 中断时间 | 净时间 | 活动 | 备注 |
| 星期一 | 14：00 | 15：50 | 10（课间） | 100 | 听课 | 软件工程上课 |
| 19：30 | 21：30 | 30 | 90 | 阅读、上网查资料 | ||
| 星期二 | 19：30 | 21：30 | 30 | 90 | 编程、阅读 | |
| 星期三 | 14：00 | 15：00 | 0 | 60 | 编程 | 数组最大子数组之和 |
| 19：00 | 20：30 | 30 | 120 | 编程 | ||
| 星期四 | 14：00 | 15：50 | 10（课间） | 100 | 听课 | 软件工程上课 |
| 16：20 | 17：30 | 0 | 70 | 编程、上网查资料 | 数组最大子数组之和2的程序 | |
| 19：30 | 21：00 | 30 | 60 | 编程 | 数组最大子数组之和2的程序 | |
| 星期五 | 14：00 | 17：00 | 60 | 120 | 编程 | 数组最大子数组之和2的程序 |
| 星期六 | 8：00 | 11：30 | 30（洗漱） | 180 | 修改，调试，发布 | 数组最大子数组之和程序进行修改、调试、写博客并发布 |