Đoạn tăng trưởng cực đại

Buổi 03 — Mảng 1 Chiều Buổi 08 — Contest Chặng 1 Implementation
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved