基本枚舉

枚舉的概念

#

枚舉是一種將所有可能的情況列舉出來的方法，是一個很常見的作法，也是非常多進階演算法的基礎。

簡單迴圈枚舉

#

枚舉的方法有很多種，最簡單的方法就是用迴圈來枚舉。
如果有一個題目要你找出這些數字中的最大值，你可以用以下的方法來解決。

int ans = 0;
for (int i = 0; i < n; i++) {
    ans = max(ans, a[i]);
}

這個範例就是用迴圈來枚舉所有的數字，並且找出最大值。
聽起來很簡單吧！

枚舉一個區間

#

給定 \(n\) 個正或負數，請你找出這些數字中最大的區間和。

在時間複雜度允許的情況下，你可以透過枚舉所有的區間來解決這個問題。那到底要怎麼枚舉區間呢？

實際上，區間可以透過兩個變數 \(l\) 和 \(r\) 來表示，\(l\) 代表區間的左端點，\(r\) 代表區間的右端點。因此，枚舉兩個變數 \(l\) 和 \(r\) 的所有可能情況，藉此枚舉所有的區間。

int ans = 0;
for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
        // 計算區間和
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += a[i];
        }
        ans = max(ans, sum);
    }
}

不過，這個方法的時間複雜度是 \(O(n^3)\)，當 \(n\) 很大時，這個方法會非常慢。因此，我們需要更好的方法來解決這個問題。

枚舉一個區間（優化版）

#

在上面的方法中，我們每次都要重新計算區間和，這樣會造成時間複雜度過高。還記得我們在前面提到的前綴和嗎？在這個情況下我們可以利用前綴和來優化這個問題！

// 計算前綴和
int ans = 0;
for (int i = 1; i <= n; i++) {
    psum[i] = psum[i-1] + a[i];
}
// 枚舉區間
for (int l = 0; l < n; l++) {
    for (int r = l; r < n; r++) {
        ans = max(ans, psum[r+1] - psum[l]);
    }
}

這個方法的時間複雜度是 \(O(n^2)\)，比起原本的方法快了很多。

從這個例子中，我們可以看到枚舉的方法有很多種，而且可以透過一些技巧來優化，讓程式更有效率。這就是為什麼枚舉常常是一個複雜問題的起手式。