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

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

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Đề 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

6

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ái8 -2 1 -3 4 -1 2 1 -5

Dữ liệu mẫu:

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

2using namespace std;

3

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}

ChậmVừaNhanhRất nhanh

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.