【现代程序设计】homework-01

HOMEWORK-01

1) 建立 GitHub 账户, 把课上做的 “最大子数组之和” 程序签入

　　已完成。

2) 在 cnblogs.com 建立自己的博客。写博客介绍自己的 GitHub 账户. 并把博客地址写到这个博客的留言。这样TA 可以收集信息

　　github：Lmeng；

　　已将信息发送到TA邮箱。

3) 搞到一本教科书 (三本中选一本), 并在博客中说明自己选的是哪一本

　　中文版代码大全 (第二版) 斯蒂夫·迈克康奈尔 ISBN: 7121022982

4) 阅读下面的博客:

　　仔细地阅读了一下这几篇文章，对自己确实有很大启发。其中所提到的效能分析是一个非常棒的方法，可以让程序员知道自己这段程序写得到底怎么样，可以在哪个部分进行优化。还有针对于自己，我还需要抓紧时间、加大努力解决低层次的问题，努力解决中层次的问题，让自己在用有限的时间花在高层次问题上。

5) 在自己的博客上描述自己是怎么设计 “最大子数组之和”这个程序的, 和正确的解法有哪些差距。

　　算法：贪心算法；

　　思路：最大子数组的子数组之和一定不大于该最大子数组之和。在该最大子数组中，前m个数和都不小于0。所以采用“过程”所描述的方法即可得到正确结果。

　　证明：最大子数组Array[n...m]的前i个数和都不小于0。m=0,1,2...m-n+1;

　　假设最大子数组为Array[n...m]，有子数组Array[n...j]，其和小于0，其中，n<j<m，下面用array[p,k]直接表示array[p]+array[p+1]+...+array[k]

　　由于Array[n...j] +Array[j...m] = Array[n...m]

　　如果Array[n...j]<0

　　那么Array[j...m]>Array[n...m]

　　所以Array[n...m]不是最大子数组。因此不存在Array[n...j]<0.得证。

　　过程：

　　1、从第一个数开始扫描数组（Array[1...n]），用tmpMaxSeq记录当前和（tmpMaxSeq = Array[1]+Array[2]+...）。

　　2、当tmpMaxSeq<0, 将它置0，

　　3、从下一个位置开始继续扫描数组。过程中出现的最大的tmpMaxSeq即为最大子数组之和。

　　复杂度：O(n)

　　心得体会：这个程序，如果想好了算法，实现起来还是比较简单的。

　　时间和效率分析：完成此次全部作业在1个小时左右。效率较高。

测试结果截屏（部分）

巴特西