Problem

21 /21


Tổng các số trong một mảng

Problem

Cho một mảng các số nguyên tùy ý. Viết chương trình trong một lần duyệt qua mảng tìm một đoạn liên tục, tổng các số trong đoạn đó là lớn nhất.
Ghi chú. Thực tế, cần phải tìm ij (i<=j) sao cho tổng của tất cả các phần tử mảng từ ai tối đa và bao gồm cả aj sẽ là giá trị tối đa.

Đầu vào
Dòng đầu tiên là một số tự nhiên n <= 100000 — số phần tử trong mảng. Các dòng n sau xác định các thành phần thực tế của — số nguyên, modulo không quá 30.000.

Dấu ấn
Xuất một cặp giá trị chỉ mục mong muốn. Nếu có một số cặp như vậy thì j phải là giá trị nhỏ nhất có thể và nếu j bằng nhau thì giá trị của i phải là giá trị lớn nhất khả thi. Trên dòng đầu tiên in i, trên dòng thứ hai - j.
 
Ví dụ
<đầu>
# Đầu vào Đầu ra
1 5
-1
2
3
-2
2
2
3
2 7
2
-2
3
-1
5
-2
7
3
7