Tổng đoạn con lớn nhất

Nguồn: Bài cơ bản Độ khó: Dễ Quy hoạch động Mảng

Đề bài

Cho dãy $n$ số nguyên $a_1, a_2, \ldots, a_n$. Hãy tìm tổng lớn nhất của một đoạn con liên tiếp khác rỗng.
Giới hạn: $1 \le n \le 10^6$, $|a_i| \le 10^9$.

Input

8
-2 1 -3 4 -1 2 1 -5

Output

Giải thích: đoạn $[4, -1, 2, 1]$ có tổng bằng $6$.

Ý tưởng

Gọi $cur$ là tổng lớn nhất của đoạn con kết thúc tại vị trí $i$. Đoạn này hoặc chỉ gồm $a_i$, hoặc nối $a_i$ vào đoạn tốt nhất kết thúc tại $i-1$: $$cur_i = \max(a_i,\; cur_{i-1} + a_i)$$ Đáp án là giá trị lớn nhất của $cur_i$ trên mọi $i$.

Em nhập dãy số rồi bấm Tiếp để xem ở mỗi vị trí $i$, thuật toán quyết định nối $a_i$ vào đoạn cũ hay bắt đầu đoạn mới:

Dãy a

Ví dụ nhanh:

Độ phức tạp

Thời gian $O(n)$, bộ nhớ $O(1)$.

Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long best = LLONG_MIN, cur = 0;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        cur = max(x, cur + x);
        best = max(best, cur);
    }
    cout << best << '\n';
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    best = float('-inf')
    cur = 0
    for x in map(int, data[1:n + 1]):
        cur = max(x, cur + x)
        best = max(best, cur)
    print(best)

main()

C++▶ Chạy tay từng dòng codeKadane: cur = tổng lớn nhất của đoạn kết thúc tại i, best = max các cur.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios::sync_with_stdio(false);

6 cin.tie(nullptr);

7 int n;

8 cin >> n;

9 long long best = LLONG_MIN, cur = 0;

10 for (int i = 0; i < n; i++) {

11 long long x;

12 cin >> x;

13 cur = max(x, cur + x);

14 best = max(best, cur);

15 }

16 cout << best << '\n';

17 return 0;

18}

Lưu ý

Tổng có thể vượt $2^{31}$, nên dùng long long trong C++.
Nếu mọi phần tử đều âm, đáp án là phần tử lớn nhất. Đừng khởi tạo best = 0.

Lập Trình Thuật Toán