CSES - Maximum Subarray Sum II | Tổng đoạn con lớn nhất II
Xem PDF
Đ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\) và \(b\).
Input
- Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(a\) và \(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 2Output
8
Bình luận
bruh bai nay O(N) cung duoc ma sao limit lai chi den 2e5
u e
tại bài này có thể làm bằng multiset á bạn
minh noi bai nay co the lam trong O(N) chu dau co bat buoc lam O(NlogN) dau
thì mình cũng tl bạn là tại sao có 2e5 á, tại dùng multiset được nên để 2e5 cg được mà
nen co 1 ban kho khoang n <= 5e6 de chi lam duoc trong O(N)