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