Đoạn con có tổng lớn nhất

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1600 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Đoạn con có tổng lớn nhất

Cho một dãy số nguyên gồm \(N\) phần tử \(A_1, A_2, ..., A_N\).

Hãy tìm một đoạn con liên tiếp có độ dài không vượt quá \(K\) sao cho tổng các phần tử trong đoạn là lớn nhất.

Input

Dòng đầu tiên chứa hai số nguyên \(N, K\)
(\(1 \le N \le 10^5\), \(1 \le K \le N\)).
Dòng thứ hai chứa \(N\) số nguyên \(A_i\)
(\(-10^9 \le A_i \le 10^9\)).

Output

In ra tổng lớn nhất của một đoạn con có độ dài không vượt quá \(K\).

Example

Test 1

Input

8 3
-2 5 -1 4 -3 6 -2 1

Output

Note

Đoạn con tối ưu là:

\(5,-1,4,?\)

Vì độ dài không được vượt quá \(3\) nên chọn:

\(4,-3,6\)

có tổng bằng \(7\) hoặc

\(5,-1,4\)

có tổng bằng \(8\).

Đáp án là \(9\) từ đoạn:

\(-1,4,-3,6\) (nếu \(K\) được mở rộng trong bộ test).

Subtask

\(100\%\) số điểm:
- \(1 \le N \le 10^5\).
- Cần sử dụng thuật toán tối ưu.

Giới hạn

Thời gian: \(1\) giây.
Bộ nhớ: \(256\) MB.

Bình luận (7)

Tải bình luận...