# 【6-0】演算法介紹

演算法（Algorithm） 是指一組「清楚定義的步驟」或「處理流程」，用來有效解決某一類問題。在程式語言的世界中，演算法不只是解題的工具，更是影響「程式效率」的關鍵因素。

- 語法讓你寫出可以執行的程式
- 邏輯賦予程式功能
- 演算法讓程式有效率、巧妙的解決問題

在[【5-0】複雜度估計法](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/B1bcXCEHgx) 我們已經學習過複雜度估計法，而複雜度正是演算法當中評斷好與壞的重要指標。

前四章學習的是基礎語法、邏輯，第五章學習的是複雜度低的工具，現在我們要把前五章學習到的內容組合起來，成為演算法。

## 範例

給定一個長度為 `n` 的整數陣列 `a[0…n-1]`，請找出一個連續子陣列，使其所有元素和最大，並輸出這個最大和。

例如，對陣列 `[-2, 1, -3, 4, -1, 2, 1, -5, 4]`，最大連續子陣列是 `[4, -1, 2, 1]`，其和為 `6`。

### 解法 1：三層迴圈暴力枚舉

最直觀的方法，枚舉所有可能的起點 `i` 和終點 `j`，累加 `a[i] + a[i+1] + … + a[j]`，並維護最大值。

int maxSubArray(vector<int>& a) {
    int n = a.size();
    int best = INT_MIN;
    // O(n²)枚舉子陣列
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            // O(n)區間和
            int sum = 0;
            for (int k = i; k <= j; ++k) {
                sum += a[k];
            }
            best = max(best, sum);
        }
    }
    return best;
}

* **時間複雜度**：O(n³)

### 解法 2：前綴和 + 雙層枚舉

利用前綴和（prefix sum）陣列 `ps`，使每次區間和計算從 O(n) 降到 O(1)。

1. 先建 `ps[0] = 0`，`ps[i] = a[0] + … + a[i-1]`。
2. 區間 `i…j` 的和就是 `ps[j+1] - ps[i]`。

int maxSubArray(vector<int>& a) {
    int n = a.size();
    // O(n)前綴和
    vector<int> ps(n + 1, 0);
    for (int i = 0; i < n; ++i)
        ps[i + 1] = ps[i] + a[i];

    int best = INT_MIN;
    // O(n²)枚舉子陣列
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            // O(1)區間和
            int sum = ps[j + 1] - ps[i];
            best = max(best, sum);
        }
    }
    return best;
}

* **時間複雜度**：O(n²)

---

### 解法 3：Kadane’s Algorithm（線性掃描）

Kadane 演算法只需一次掃描，就能在 O(n) 內解出最大和。思路是：

1. 設 `curr = a[0]`, `best = a[0]`
2. 每向右移一格 `i`，更新

   curr = max(a[i], curr + a[i]);
   best = max(best, curr);

其中 `curr` 代表「以 i 結尾的最大子陣列和」。

int maxSubArray(vector<int>& a) {
    int n = a.size();
    int curr = a[0], best = a[0];
    // O(n)線性掃描找以 i 結尾的最大子陣列和
    for (int i = 1; i < n; ++i) {
        curr = max(a[i], curr + a[i]);
        best = max(best, curr);
    }
    return best;
}

* **時間複雜度**：O(n)

## 結論

在接下來的單元，我們將著重介紹各類演算法的思路，並提供範例來講解演算法在題目中的應用，比較同一題的各類演算法效率，建議讀者熟讀第五章及以前的所有內容，再來看演算法。

---

聯絡方式：[e-mail]
最後編修時間：2025/08/02 子柚筆