Bài tập ngày 30/8
Dãy con không giảm
Nộp bài
Time limit: 1.0 /
Memory limit: 256M
Point: 5
Cho một dãy số gồm n số nguyên dương ~a_1, a_2, …, a_n~ (~1 ≤ a_i ≤ 10⁵, 1 ≤ i ≤ n ≤ 10⁵~).
Xét các dãy con là dãy các phần tử liên tiếp nhau của dãy ban đầu, mà trong đó các phần tử là không giảm (~a_i ≤ a_{i+1} ≤ … ≤ a ≤ aⱼ₊₁ ≤ … ≤ aᵣ~).
Yêu cầu:
Tìm dãy con có tổng các phần tử là lớn nhất trong các dãy con trên, nếu có nhiều dãy con thỏa mãn thì in ra các dãy con lần lượt theo vị trí xuất hiện, mỗi dãy con in trên một dòng.
Dữ liệu:
- Dòng đầu tiên ghi số nguyên dương n;
- Dòng tiếp theo ghi n số nguyên dương, mỗi số cách nhau một khoảng trắng.
Kết quả:
- Dòng đầu tiên ghi tổng các phần tử của một dãy con tìm được theo yêu cầu;
- Các dòng tiếp theo, mỗi dòng ghi ra các phần tử của một dãy con tìm được.
Ví dụ:
SUBSEQ.INP
10
2 2 3 4 6 6 7 7 8 8
SUBSEQ.OUT
53
2 2 3 4 6 6 7 7 8 8
SUBSEQ.INP
11
4 7 4 5 7 4 9 3 3 4 6
SUBSEQ.OUT
16
4 5 7
3 3 4 6
Ràng buộc:
- Có 20% số điểm ứng với ~n = 10~ và dãy ban đầu là một dãy không giảm;
- Có 20% số điểm ứng với (~11 ≤ n ≤ 200~);
- Có 20% số điểm ứng với (~201 ≤ n ≤ 10³~);
- 40% số điểm còn lại ứng với (~10³ < n ≤ 10⁵~).
