【演算法】最大連續子序列和（Max Subarray Sum）

發布於 分類於 ， 閱讀次數： 文章字數： 208 所需閱讀時間 ≈ 1 分鐘

簡介

題目要求我們從 [1, 2, -4, 5 -2, 6, 2] 數列中找出最大的子序列和為 11

解法 1：暴力解

時間複雜度為：O(n3)O(n^3)

真的太大了，可以忽略不記這種解。

解法 2：卡丹算法（Kadane’s Algorithm）

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

簡單說明就是決定子序列是否要加上當前值，或是重新開始一個子序列。

基本上，一邊輸入一邊判斷是否加起來就可以直接用一個一層 for 迴圈解決。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;

int main() {
    int n;
    cin >> n;
    ll arr[n], sum = 0, mx = LONG_LONG_MIN;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        (i == 0) ? sum = arr[i] : sum = max(arr[i], sum + arr[i]);
        mx = max(mx, sum);
    }

    cout << mx << "\n";
}

題目

  • CSES Maximum Subarray Sum