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