CSES - Maximum Subarray Sum II | Tổng đoạn con lớn nhất II

Xem PDF



Tác giả:
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một đoạn con liên tiếp với độ dài giữa \(a\)\(b\).

Input

  • Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(a\)\(b\): kích thước của mảng và độ dài tối thiểu và tối đa của đoạn con.
  • Dòng thứ hai có \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các giá trị mảng.

Output

  • In một số nguyên: tổng đoạn con lớn nhất.

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le a \le b \le n\)
  • \(-10^9 \le x_i \le 10^9\)

Example

Test 1

Input
8 1 2
-1 3 -2 5 3 -5 2 2
Output
8

Bình luận