Spoiler Alert

Hint 1

• Tìm dãy con có tổng lớn nhất

Ý tưởng cơ bản: Thử tất cả các dãy \(a_i, a_j, ...\) và tìm dãy có tổng lớn nhất

• Tìm đoạn con có tổng lớn nhất

Ý tưởng cơ bản: Thử tất các các đoạn \((i, j)\) và \((i \leq j)\) và tìm đoạn có tổng lớn nhất

Hint 2

• Tìm dãy con tổng lớn nhất

Gọi \(sum1\) là tổng ở hiện tại

Nhận xét rằng \(sum1 + x < sum1\) khi \(x < 0\)

Nhận xét rằng \(sum1 + x \geq sum1\) khi \(x \geq 0\)

• Tìm đoạn con có tổng lớn nhất

Gọi \(curr\) là giá trị lớn nhất đến hiện tại

Gọi \(sum2\) lá giá trị cực đại của \(curr\)

Nhận xét rằng \(curr + x < x\) khi \(curr < 0\)

Nhận xét rằng \(curr + x \geq x\) khi \(curr \geq 0\)

Hint 3

• Tìm dãy con tổng lớn nhất

Trong trường hợp mảng chí toàn âm: Ta tìm số âm lớn nhất

Trong trường hợp mảng có số không âm: Ta tính tổng tất cả các số không âm

• Tìm đoạn con có tổng lớn nhất

Trong trường hợp \(curr\) âm, ta thay \(curr = x\)

Trong trường hợp \(curr\) dương, ta thêm \(curr\) đại lượng \(x\)

\(sum2 = max(curr)\) tại mọi thời điểm

Hint 4

• Tìm dãy con tổng lớn nhất

\(sum1 = max(sum1, max(sum1 + temp, temp));\)

• Tìm đoạn con có tổng lớn nhất [Kadane Algorithm]

\(curr = max(temp, curr + temp);\)

\(sum2 = max(sum2, curr);\)

Reference AC code | \(O(n)\) time | \(O(1)\) auxiliary space | Online Solving, Greedy, DP

int query()
{
    int sum1 = -INF;
    int sum2 = -INF, curr = 0;
    for (int n = readInt(); n--; ) {
        int temp;
        cin >> temp;
        sum1 = max(sum1, max(sum1 + temp, temp));
        curr = max(temp, curr + temp);
        sum2 = max(sum2, curr);
    }

    cout << sum1 << ' ' << sum2 << '\n';
    return 0;
}