程序思路:
一维的主要思想是:最大序列的初始项一定是正数,然后在此项基础上向后遍历,当该连续序列的的总和小于或等于0时,就是这个序列的断点,因为若把该序列当做一个数则为负数,一定不是另一个序列的初始。所以统计该序列的最大值,由addornot决定。这样可以把数组分成若干个独立的序列,然后这些序列都有一个最大值,他们中的最大值就是整个数组的最大者。
二维建立在一维原理差不多,主要思想是以起始行为变量,把二维数组的多行的同列相加合并成一行,然后进行一维的运算,若矩阵为n*n,则起始行和结束行共有(n+1)*n/2;
最后的算法复杂度为O(n^3);
心得:
在这个程序中我没有使用老师推荐的动态规划,而是自己对问题的分析然后找到规律得出结论。
结果的截图:
所选书籍:Personal Software Process