Tổng dãy con

Thời gian:

Python 3 3.0s

Bộ nhớ:

Python 3 260M

Tác giả:

admin

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
Dãy con gồm các phần tử liên tiếp có tổng lớn nhất.

Input

Gồm nhiều test, dòng đầu tiên là số lượng test \(T\) \((1≤T≤10)\)
Mỗi bộ test gồm hai dòng:
- Dòng đầu là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
- Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu.

Example

Test 1

Input

2
3
4 4 2
5
3 3 -2 3 -4

Output

10 10
9 7

Bình luận

7
SPyofgame 3:52 p.m. 15 Tháng 6, 2020
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

C++
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; }