Dùng giải thuật Kadane.

Duyệt từng phần tử, giữ biến \(cur\) là tổng lớn nhất của đoạn con kết thúc tại vị trí hiện tại:

• \(cur = max(a_i, cur + a_i)\)
• \(best = max(best, cur)\)

Độ phức tạp \(O(N)\).

Hướng dẫn giải

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Mã nguồn C++

// Giải thuật ps cho bài toán ps-max-sub\n#include <bits/stdc++.h>
using namespace std;

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(0); cin.tie(0);
    // TODO: implement solution
    cout << "\n";
    return 0;
}