1. 题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
2. 设计思想
这个程序乍一看特别简单，一个新手都会，但仔细一想，才发现其中的难度。空间复杂度为O（n），这个就比较难了。、
首先产生N个随机数，下面就是核心部分，
我的想法是用for循环，但是根据题目要求只能用一次循环，想了很久才发现，可以进行一次次判定，我把我的思想分成来两部分：
1. 在这个循环中，把前几个相加，看是否是整数。
2. 其次看（i+1）的和是否大于（i）的和。
根据这就可以用一个循环来进行计算。接下来就是考虑其他的问题，比如最大子数组的起始位置和最终位置。把这个加入到for循环中，用if条件语句进行判断。最后输出即可。
3. 源代码
import java.util.Random; import java.util.Scanner; public class main { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int a[]=new int[100]; int sum,d,temp1=0,temp2=0,flag1=0,flag2=0; //分别记录子数列的起始和结束位置 System.out.print("请输入数组元素的个数：（小于100） "); Scanner sc=new Scanner(System.in); int m=sc.nextInt(); Random rand = new Random(); for(int i=0;i<m;i++)//循环为数组赋值 { a[i] = rand.nextInt(40)-20; System.out.print(a[i]+" "); } sum=a[0]; d=sum; for(int i=0;i<m;i++)//核心循环，来判断怎么产生最大子数组 { if(d<=0){ d=0; temp1=i+1; temp2=i; } d+=a[i+1]; temp2++; if(d>sum){ sum=d; flag1=temp1; flag2=temp2; } } System.out.println(""); System.out.print("子数组的组成元素为： "); for(int i=flag1;i<=flag2;i++) System.out.print(a[i]+" "); System.out.println(""); System.out.println("子数组和的最大值为： "+sum); } }
4. 运行结果截图
5. 周活动总结表
周活动总结表
姓名：张晨建 日期：2015-03-23
|
听课 |
编写程序 |
阅读课本 |
日总计 |
|||
|
周日 |
70 |
30 |
100 |
|||
|
周一 |
240 |
20 |
260 |
|||
|
周二 |
500 |
500 |
||||
|
周三 |
120 |
60 |
180 |
|||
|
周四 |
360 |
40 |
400 |
|||
|
周五 |
360 |
20 |
380 |
|||
|
周六 |
120 |
80 |
60 |
260 |
||
|
周总计 |
1900 |
210 |
170 |
2280 |
阶段时间和效率 周数（上一周活动总结的周数+1）:1
不包括在上一周内的累计时间
|
总计 |
1700 |
100 |
20 |
1820 |
||
|
平均 |
1700 |
100 |
20 |
1820 |
||
|
最大 |
1700 |
100 |
20 |
1820 |
||
|
最小 |
1700 |
100 |
20 |
1820 |
以前各周的累计时间
|
总计 |
1700 |
100 |
20 |
1820 |
||
|
平均 |
1700 |
100 |
20 |
1820 |
||
|
最大 |
1700 |
100 |
20 |
1820 |
||
|
最小 |
1700 |
100 |
20 |
1820 |
6. 时间记录日志：
学生：张晨建 日期：3/23/2015
教师：王建民 课程：软件工程概论
|
日期 |
开始时间 |
结束时间 |
中断时间 |
净时间 |
活动 |
备注 |
|
3-20 |
10:10 |
12:00 |
10 |
100 |
上课 |
软件时间概论 |
|
3-20----3-21 |
剩余时间上课和休息 |
|||||
|
3-22 |
9；00 |
11:30 |
0 |
150 |
编程 |
|
|
3-23 |
4:00 |
7:00 |
0 |
180 |
编程 |
7. 缺陷记录日志
学生：张晨建 日期：3/23/2015
教师： 王建民 程序：数组
|
日期 |
编号 |
修复时间 |
修复缺陷 |
描述 |
|
3-22 |
1 |
20 |
产生随机负数 |
修复了无法产生随机负数的bug |
|
3-23 |
2 |
120 |
求最大数组 |
修复了求最大子数组一直出现全部的bug |