Tổng liên tiếp (Bài 3 HSG9 Tỉnh Bà Rịa - Vũng Tàu 2025)

Xem PDF

Đ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\)\(|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

Không có bình luận nào.