1) 一维数组最大连续子数组
如第homework-01就是一维数组的最大子数组，而当其首位相接时，只需多考虑子数组穿过相接的那个数就行了！
2）二维数组
算法应该和第一次的相似，或者说是将二维转化为一维。
直接采取上下界枚举，得出结果。
部分代码如下
int maxsumh(int a[][COL], int row, int col) { int i, j, start; int max, min, temp; int summax, summin, sumall; int sum[ROW][COL]; temp = a[0][0]; for (i = 0; i < row; i++) for (j = 0; j < col; j++) temp = MAX(a[i][j], temp); if (temp < 0) return temp; for (start = 0; start < row; start++) { for (j = 0; j < col; j++) { for (i = start; i < row; i++) { if (i == start) sum[i][j] = a[i][j]; else sum[i][j] = a[i][j] + sum[i - 1][j]; } } for (i = start; i < row; i++) { max = min = sum[i][0]; for (j = 0; j < col; j++) { max = MIN(sum[i][j], max); min = MAX(sum[i][j], min); } sumall = summax = summin = 0; for (j = 0; j < col; j++) { sumall += sum[i][j]; summax += sum[i][j]; summin += sum[i][j]; max = MAX(max, summax); min = MIN(min, summin); summax = MAX(summax, 0); summin = MIN(summin, 0); } temp = MAX(temp, MAX(sumall - min, max)); } } return temp; }
代码时间复杂度为O(n^3)，但空间复杂度就很大，导致数组大小限制比较严重，我开数组行，列很大时，容易造成运行堆栈溢出。不怎么会做优化，就没有做了。
1、描述在这么多相似的需求面前, 你怎么维护你的设计 (父类/子类/基类, UML, 设计模式, 或者其它方法) 让整个程序的架构不至于崩溃的?
我是每种要求单独设计一个方法函数，直接调用。
2、你在这个作业中学到了什么? 有什么好的设计值得分享? 感想如何 (太容易 / 太难 / 太无趣)?
个人感觉题目对我来说难度很大。
|
Personal Software Process Stages |
时间百分比(%) |
实际花费的时间 (分钟) |
原来估计的时间 (分钟) |
|
|
Planning |
计划 |
|||
|
· Estimate |
· 估计这个任务需要多少时间，把工作细化并大致排序 |
|||
|
Development |
开发 |
|||
|
· Analysis |
· 需求分析 (包括学习新技术) |
6% | 30 | 30 |
|
· Design Spec |
· 生成设计文档 |
4% | 20 | 20 |
|
· Design Review |
· 设计复审 (和同事审核设计文档) |
0 | 0 | 0 |
|
· Coding Standard |
· 代码规范 (制定合适的规范) |
2% | 10 | 20 |
|
· Design |
· 具体设计 |
24% | 120 | 60 |
|
· Coding |
· 具体编码 |
24% | 120 | 60 |
|
· Code Review |
· 代码复审 |
0 | 0 | 0 |
|
· Test |
· 测试（自我测试，修改代码，提交修改） |
40% | 200 | 30 |
|
Reporting |
总结报告 |
|||
|
||||
|
||||
| Total | 总计 | 100% | 总用时 500 | 总估计的用时 220 |