最大子數列

非循環陣列

給定長度為 N 的整數陣列A，從 A 所有可能的 subarray 中找出一個 subarray S，使得 S 中所有元素的總和是最大值。

Kadane’s Algorithm

循環遍歷整個陣列 A，在第 i 個元素時判斷 A[i] 和 cucursum + A[i] 的大小，判定在第 i 個元素時所能達到的最大值，之後將 cursum 與 maxsum 比較，取得子字串總和的最大值。

程式碼：

1
2
3
4
5
6
int maxsum = A[0], cursum = 0;  
for(int i = 0; i < N; i++){  
    cursum = max(cursum + A[i], A[i]);  
    maxsum = max(maxsum, cursum);
}
retuen maxsum;

因為只要遍歷整個陣列一次，時間複雜度為 O(n)。

循環陣列

給定長度為 N 的 “循環” 整數陣列A，從 A 所有可能的 subarray 中找出一個 subarray S，使得 S 中所有元素的總和是最大值。

因為在尋找最大子數列時，可能會有數列跨越 A[N-1] 到 A[0] 的情況，這時候除了該數列之外，剩下的部分就可以利用之前的方式處理，找到最小子數列，那剩餘的部分就會是最大子數列，可以得到答案為 max(total - minsum, maxsum)，其中 total 為整個陣列總和。
另外必須考慮陣列元素全為負數時 total - minsum = 0，必須回傳 maxsum，也就是陣列元素中的最大值。
程式碼：

1
2
3
4
5
6
7
8
9
10
int maxsum = A[0], cursum1 = 0, minsum = A[0], cursum2 = 0, total = 0;  
for(int i = 0; i < N; i++){  
    total += m[i];  
    cursum1 = max(cursum1 + A[i], A[i]);  
    maxsum = max(maxsum, cursum1);  
    cursum2 = min(cursum2 + A[i], A[i]);  
    minsum = min(minsum, cursum2);  
}  
if(total == minsum) retuen maxsum;
else retuen max(total - minsum, maxsum);

判斷陣列元素是否全為負數的特例情況時，也可以透過 maxsum < 0 來作為條件。

數島嶼

給定一個 M * N 的二維矩陣地圖，矩陣中的值只有 0 或 1，分別代表陸地和海洋。由多個相鄰的陸地水平或垂直連接而形成的區塊稱為一個島嶼，且陸地之間不能以斜向方式連接。請找出在地圖中所有島嶼的數量。

遍歷整個陣列，當遇到陸地時將島嶼數加一，進行 DFS 尋找鄰近的其他陸地，並且直接把該陸地炸沉 (1 改為 0) 避免再次訪問到。
DFS 函式程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void check (int x, int y, int m, int n, int arr[300][300]){  
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  
    if(arr[x][y] == 0) return; //判斷是否為陸地
    else{  
        arr[x][y] = 0; //炸沉陸地
        for(int i = 0; i < 4; i++){  
            int tx = x + dir[i][0], ty = y + dir[i][1];
            //判斷邊界
            if(tx >= 0 && tx <= m-1 && ty >= 0 && ty <= n-1){  
                check(tx, ty, m, n, arr);  
            }  
        }  
    }  
}