Dãy con không giảm
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
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⁵~).
Bình luận
khó vcl shop ơi