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


  • -1
    hungcubuso1vn    6:43 p.m. 24 Tháng 3, 2024

    bruh bai nay O(N) cung duoc ma sao limit lai chi den 2e5


    • 0
      hungcubu    1:13 p.m. 1 Tháng 6, 2024

      u e


      • 0
        chienthancontent    8:44 p.m. 13 Tháng 5, 2024

        tại bài này có thể làm bằng multiset á bạn


        • -1
          hungcubuso1vn    7:46 p.m. 14 Tháng 5, 2024

          minh noi bai nay co the lam trong O(N) chu dau co bat buoc lam O(NlogN) dau


          • 0
            chienthancontent    9:18 a.m. 16 Tháng 5, 2024

            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à


            • -1
              hungcubuso1vn    9:08 p.m. 16 Tháng 5, 2024

              nen co 1 ban kho khoang n <= 5e6 de chi lam duoc trong O(N)