在解決一個問題的時候，常常最直接的作法就是「把所有解決方案都列出來看看」，像是決定午餐要吃哪家餐廳時，把附近所有的餐廳列出來，並且找到這些餐廳中現在最想吃的，這個「一一列出來」的作法就稱為枚舉。

「列出所有可能性」在可能性很多的時候，人不太可能做到，雖然電腦的計算能力比人類好上許多，但要枚舉的東西可能會長得奇形怪狀，或者亂枚舉之下仍然有過多可能性，電腦也不能快速解決，因此如何正確且快速的枚舉我們想要的東西是一個問題。

最基本的枚舉，就是枚舉一些簡易的物件，像是題目輸入的東西們、某個範圍裡的整數之類的，只要一個簡單的迴圈就能舉出所有東西。不過枚舉的對象也可以很複雜，接下來我們會介紹兩種常見的枚舉對象：排列與集合。

一個序列的排列（permutation）指的就是把這個序列中的元素亂換順序後，能得到的所有可能的序列，像是 $[1,2,2,4]$ 的排列就有
\[
\begin{array}{ccc}
[1,2,2,4] &
[1,2,4,2] &
[1,4,2,2] \\
[2,1,2,4] &
[2,1,4,2] &
[2,2,1,4] \\
[2,2,4,1] &
[2,4,1,2] &
[2,4,2,1] \\
[4,1,2,2] &
[4,2,1,2] &
[4,2,2,1]
\end{array}
\]

要枚舉所有的排列很簡單，<algorithm> 裡的 next_permutation() 都幫我們做好了：

int a[n] = { /* ... */ };
sort(a, a + n);
do {
    // do something...
}
while(next_permutation(a, a + n));

這樣一來每次 do 裡面的區塊執行的時候，a 都會是不同的 permutation，而且每個 permutation 都會被枚舉過一次。

next_permutation(l, r) 代表的是把 $[l,r)$ 範圍裡的部分，變成「下一個排列」，如果這個排列是「最後一個排列」的話，就會變成「第一個排列」並且回傳 false，反之如果成功變成下一個排列，就會回傳 true。也就是這個數列的所有排列們被排了一個順序，next_permutation() 會幫我們拿到傳進去的排列的下一個（或變回第一個），這個順序是字典序（lexicographical order），像上面列出的 $[1,2,2,4]$ 的排列，就是按照字典序順序列出的。

舉例來說，$[2,1,2,4]$ 傳進 next_permutation() 之後，就會變成 $[2,1,4,2]$ 並且回傳 true、傳進 $[4,2,2,1]$ 會變成 $[1,2,2,4]$ 並且回傳 false，因為它沒有下一個排列了。可以發現到第一個排列肯定是從小到大排序的那一個，這也是為什麼上面的程式碼一開始要先將 a 排序，這樣子才會從第一個排列開始枚舉。（所以如果 a 一開始就排序好，就不需要再排序了。）

一次 next_permutation() 的最差時間複雜度是 $O(N)$，聽起來如果枚舉所有的排列一次，複雜度最差會到 $O(N \times N!)$（$1,2,\dots,N$ 的排列有 $N!$ 個），不過總複雜度其實會神奇地是 $O(N!)$。（只是指單純跑過上面那個迴圈，當然你在迴圈裡有做別的事就另當別論了。）

既然題目要的是「字典序最小的可能的 $p$」，那麼我們可以從最小字典序的排列（也就是 $[1,2,3,4,5,6]$）開始，按照字典序枚舉所有長度為 6 的排列，枚舉一個排列時檢查它可不可以是 $p$，只要找到一個可以當作 $p$ 的排列就輸出答案。

#include <bits/stdc++.h>
using namespace std;

int a[6][6];
int cnt[6];

int main() {
    
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) cin >> a[i][j];
        cin >> cnt[i];
    }

    int p[6] = {1, 2, 3, 4, 5, 6};

    do {
        bool ok = true;
        for (int i = 0; i < 6; i++) {
            int tmp = 0;
            for (int j = 0; j < 6; j++) {
                if(p[j] == a[i][j]) tmp++;
            }
            if (tmp != cnt[i]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            for (int i = 0; i < 6; i++) cout << p[i] << " \n"[i == 5];
            break;
        }
    }
    while (next_permutation(p, p + 6));

}

集合是另一個經常需要枚舉的東西。具體來說，通常是要枚舉像是 $\{0,1,\dots,N-1\}$ 這種集合的一個子集，也就是所有挑一些不重複東西出來的方法。

在處理集合相關的東西的時候，我們通常會使用一個非負整數來表示一個集合，這個數在二進位下的第 $i$ 個位數是 $1$ 就代表集合中包含 $i$。例如 $163_{(10)}=10100011_{(2)}$ 就代表 $\{0,1,5,7\}$ 這個集合。

在知道要用一個數字來表示集合之後，枚舉集合的方法就呼之欲出了！要枚舉 $\{0,1,\dots,N-1\}$ 的一個子集合只需要枚舉 $0$ 到 $2^{N-1}$ 的所有整數，像是：

for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
        if ((1 << j) & i) cout << j << " "
    }
    cout << "\n";
}

(1 << j) & i 可以檢查 $i$ 的第 $j$ 個 bit 是不是 1，1 << j 就是 $2^j$，也就是二進位下只有第 $j$ 位是 1 的數字。

我們學會怎麼枚舉奇怪的東西了，但也不能總是暴力地把所有東西都枚舉出來，而是要聰明地只枚舉其中一些東西。在枚舉的同時，也可以利用一些聰明的方式來加快。

枚舉所有 $1$ 到 $N$ 之內的三個整數 $a,b,c$？顯然是有更好的作法，像是只要知道 $a,b$，就能知道 $c$ 一定只能是 $\sqrt{a+b}$ 了，然而 $\sqrt{a+b}$ 不見得會是整數，這樣我們不僅會浪費時間在不可能是答案的東西，這個浪費的時間還很多，$(a,b)$ 的數量可是多達 $O(N^2)$ 種。

但如果是枚舉 $a,c$ 的話，我們就會知道 $b=c^2-a$，這一定是個整數！所以這樣做的話，我們就不會浪費時間在枚舉不重要的東西了。$c$ 的最大值是 $\sqrt{N}$，所以答案的數量以及我們花的時間就只有 $O(N \sqrt{N})$ 而已。

既然這題問的是「最大總和的區間」，最直覺的想法就是直接枚舉全部的區間 $[l,r]$，如果先枚舉所有的左右界，然後再暴力掃過一次整個區間計算總和，把所有總和取 max，這樣總時間複雜度是 $O(n^3)$，實在是太久了。

要把時間降到 $O(n^2)$ 的方法有很多，像是固定左界的時候，可以從左到右枚舉右界，一邊維護現在枚舉的到區間的總和，把右界往右移一格時，把總和多加上加進來的那個數字就好，這樣就不需要對每一個區間的重算一次總和了。另一種方法是利用前綴和：

\[ \begin{array}{cl}
& \phantom{(}x_1+x_2+\dots+x_{l-1}+x_l+x_{l+1}+\dots+x_r \\
-& (x_1+x_2+\dots+x_{l-1}) \\ \hline
=& \phantom{(x_1+x_2+\dots+x_{l-1})+}x_l + x_{l+1} + \dots + x_r
\end{array}\]

所以我們只要先算出所有的 $s_i=x_1+\dots+x_i$（$s_0$ 就是什麼都沒加，所以 $s_0=0$），就可以在知道左右界 $l,r$ 的時候，馬上得出來 $[l,r]$ 這個區間的總和就是 $s_r-s_{l-1}$。

如果我們希望複雜度是 $O(n^2)$，計算 $s_i$ 當然可以對每個 $i$ 都暴力計算 $x_1+\dots+x_i$，不過也有一個聰明一點的作法：$s_i=x_1+\dots+x_{i-1}+x_i$ 其實就是 $s_i=s_{i-1}+x_i$，這樣就只要枚舉 $i=1$ 到 $n$，依序計算 $s_i$ 就可以在 $O(n)$ 的時間算出來了。

不過 $O(n^2)$ 還是太久了，要降到更低的時間複雜度，我們就不可能枚舉全部的區間。我們剛剛枚舉了兩個東西：$l$ 和 $r$，那如果我們只枚舉其中一個呢？假設我們選擇枚舉 $r$，沿用前綴和的想法，在固定 $r$ 的時候，$s_r$ 就是已知的，我們的目標是找到最大的 $s_r-s_{l-1}$，既然 $s_r$ 是固定的，那麼我們的目標其實就是找一個最小的 $s_{l-1}$，並且要滿足 $l - 1 < r$。

發現了嗎？只要我們是從小到大枚舉 $r$，我們在處理一個 $r$ 之前，就已經看過所有 $<r$ 的位置了，所以我們只要記錄下之前看過的最小的 $s_i$，直接拿它來當 $s_{l-1}$ 就可以了。甚至我們還不需要把整個前綴和存下來，只要一邊計算前綴和，一邊記下看過的最小前綴和，再拿去和目前的前綴和相減，整個過程拿到的最大值就是答案了。如此一來我們就在 $O(n)$ 的時間解決了這個問題。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    int n;
    cin >> n;

    ll s = 0;
    ll mn = 0;
    ll ans = -LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        s += x;
        ans = max(ans, s - mn);
        mn = min(mn, s);
    }
    cout << ans << "\n";
}

這裡幫讀者總結一些枚舉的思考策略：

• 讓一些東西固定：像是在枚舉排列或集合時，我們做的事情是「每次都固定一個排列或者集合，只思考這個排列或集合有關的事情」、在找最大連續和時，我們每次都固定右界，然後思考選哪個左界比較好。在枚舉的時候，可以暫時不用在意目前枚舉的項目之外的可能性，專注於目前枚舉到的東西上。
• 選擇好的枚舉物件：像是在找 $a+b=c^2$ 的解時，我們應該要選擇枚舉 $a,c$ 而不是枚舉 $a,b$，在想怎麼枚舉時，可以想想如果有些資訊是已知的，那是不是有其他資訊我們直接就可以知道，不需要再另外枚舉，以及枚舉哪一些東西可以比較省時間或是比較好處理。
• 用正確的枚舉順序：像是在算前綴和時，從前算到後的話，就可以簡單又快速地算出來。在後面的許多主題裡，都會需要使用特定的順序去枚舉東西。除了正著掃、倒著掃等等的順序以外，也有可能是要先排序再枚舉之類的特殊順序。