Tổng k số

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 0.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

In ra đáp án thỏa mãn yêu cầu đề bài.

Example

Test 1

Input

6 2
2 4 5 2 9 1

Output

Bình luận

include <bits/stdc++.h>

using namespace std;

int main()
{
int n, k;
cin >> n >> k;

vector<int> a(n);
for (int &x : a) cin >> x;

long long sum = 0;
for (int i = 0; i < k; ++i) sum += a[i];

long long res = sum;
for (int i = k; i < n; ++i) {
    sum += a[i] - a[i - k];
    res = max(res, sum);
}

cout << res;
return 0;

}
CODE AC

9 bình luận nữa