Điểm:
1 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một dãy \(A\) gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\).
Yêu cầu: Hãy tìm đoạn con \([l, r]\) \((1 \le l \le r \le n)\) gồm các phần tử liên tiếp \(A_l, A_{l+1}, \dots, A_{r-1}, A_r\) của dãy \(A\) sao cho tổng \(A_l + A_{l+1} + \dots + A_{r-1} + A_r\) là lớn nhất
Dữ liệu
Vào từ file văn bản MAXS.INP:
- Dòng đầu tiên chứa số nguyên \(N\).
- Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\).
Dữ liệu đảm bảo: \(1 \le N \le 10^5\) và \(|A_i|\le 10^9\).
Kết quả
Ghi vào file văn bản MAXS.OUT một số nguyên là tổng lớn nhất tìm được.
Ràng buộc
- Subtask 1: \(20\%\) số test ứng với \(1 \le N \le 100\)
- Subtask 2: \(20\%\) số test ứng với \(1 \le N \le 10^4\)
- Subtask 3: \(20\%\) số test ứng với \(A_i \ge 0\).
- Subtask 4: \(40\%\) số test không có ràng buộc gì thêm.
Ví dụ
Test
Input
6
2 -3 8 4 -5 3
Output
12
Note
\(A_3 + A_4 = 8 + 4 = 12\).
Bình luận