结对小组：张永&吴盈盈
每到周一，建民老师都会在课堂上留下一个引人深思的问题。题目：求一个二维数组中子数组和最大的子数组，子数组只要由连续的元素组成即可。
例如：
对这个题目的分析：
1.首先应该对个二维数组遍历一遍，求出二维数组中所有的正数，并记录每个正数所对应的位置（行号和列号）；
2.对遍历到的所有的正数进行排序（由大到小），要求只要连续的字块的和的最大值，首先从二维数组中最大的正数（设为a）开始找。找a到次大的正数（设为b）之间的一条路径，这条路径满足的条件是，路径上所有元素的和加起来的绝对值要小于b；
这个路径不一定是最近的。
下面的问题就转到了求两点之间的最短路径问题，我们可以借助A*算法来计算。
A*算法的伪代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 |
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。 算起点的估价值; 将起点放入OPEN表; while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点){ break; } for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ){ 把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值 } } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ){ 把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值 } } if(X not inboth){ 把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序 } }//end for 将n节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最 小路径的节点向下进行。 }//end while(OPEN!=NULL) 保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径 |
A*算法详解参考http://www.cnblogs.com/kanego/archive/2011/08/30/2159070.html
3.然后在以a,b为端点，再寻找到第三大的值得路径。
把所有的正数都遍历一遍，得到的连续的字块的值就是最大的。
结对开发求二维数组值最大的子数组（只要连续即可）,布布扣,bubuko.com
原文：http://www.cnblogs.com/zhangyongJava/p/3629866.html