Đoạn tăng trưởng cực đại
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho dãy lợi nhuận theo ngày gồm $N$ số nguyên $a_1, a_2, \dots, a_N$. Hãy tìm một đoạn con liên tiếp $[L, R]$ ($1 \le L \le R \le N$) có tổng lớn nhất. Nếu có nhiều đoạn cùng đạt tổng lớn nhất, chọn đoạn có $L$ nhỏ nhất; nếu vẫn bằng nhau thì chọn đoạn có $R$ nhỏ nhất.
Dữ liệu vào
Dòng đầu chứa số nguyên $N$. Dòng thứ hai chứa $N$ số nguyên $a_1, \dots, a_N$.
Dữ liệu ra
In ra 3 số nguyên trên một dòng: tổng lớn nhất, $L$ và $R$.
Ví dụ
| Input | Output |
|---|---|
| 6 -2 1 -3 4 -1 2 |
5 4 6 |
| 3 -5 -2 -8 |
-2 2 2 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
Community Discussion