1. 首先我们先看一维的整数,并想办法去求出此一维整数的最大和 例. -1 4 -3 2 -2 我们要怎麽求出在这个整数array中最大的一段连续整数的和呢? 作法如下: { int i,j,A[5]; (A[0]~A[4]分别是-1 4 -3 2 -2) int B[5]; B[0] = A[0]; for(i=1;i<5;i++){ if(B[i-1]<0) B[i] = A[i]; //B[i]纪录的是以A[i]为结尾中而前面i-1个整数为开头 //的这一串连续整数的总和为最大的值, //而B[i]的决定方式则是看B[i-1]是否大於0, //如果B[i-1]<=0,则到B[i]为止最大的整数和即为A[i], //而若B[i-1]>0,则最大的整数和即为B[i-1]+A[i], //接着花time complexity O(n)的时间就可以做完B array, //紧接着只要在B array中找到最大的一个整数即为所求. else{ B[i] = B[i-1] + A[i]; } } int temp = -1000; for(i=0;i<5;i++) if(temp<B[i]) temp = B[i]; return temp; } 2.接下来则是要利用1的方法推广到2维的integer array上 概念跟1一样,求一个sub rectangle中的整数和最大 我们要try过所有这个sub rectangle的上下边界(即row) 例如如果我们假设最大的rectangle的上下两个边界分别是在 第一个row和第3个row 那以下的这个array我们就可以把他第1,2,3个row的相对位置加起来 形成一个新的一维的array,而我们的目的就会等同於去求这个一维array的最大 连续整数的最大和, 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 0 -2 -7 0 9 2 -6 2 +|-4 1 -4 1 -------------- A: 5 1 -17 3 ==> B: 5 6 -6 3 所以最大的整数和即为6 ( | 0 -2 | | 9 2 | | -4 1 | ) 所以我们要try过 n * (n-1) /2个组合 (time complexity O(n^2) ) 而每做一次这样的try则需要time complexity O(n) 而为了减少每次连续rows的相加所花的时间我们利用: 假设原array为 A1:... A2:... . . . An:... 我们将这笔资料存成以下的格式 B1:... B2:... . . . Bn:... B1 = A1 Bi = (Bi-1) + Ai (time complexity O(n^2)) 此时若要try第a行与第b行中的最大整数和 则可以利用Bb - (Ba-1)得到一维阵列再求即可 ( time complexity O(n) ) 可以减少一些重复计算 所以整个演算法的time complexity就是O(n^3) the end --

※ 发信站: 批踢踢实业坊(ptt.csie.ntu.edu.tw) ◆ From: 140.112.30.60