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

Spoiler Alert

Code mang tính tham khảo

Sliding Window || O(n) space

C++

int main()
{
    int n = readInt();
    int k = readInt();

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

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

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

    cout << res;
    return 0;
}

Sliding Window using Deque | O(k) space

C++

int main()
{
    int n = readInt();
    int k = readInt();

    ll sum = 0;
    deque<int> S;
    for (int i = 0; i < k; ++i)
    {
        S.push_back(readInt());
        sum += S.back();
    }

    ll res = sum;
    for (int i = k; i < n; ++i)
    {
        S.push_back(readInt());
        res = max(res, sum += S.back() - S.front());
        S.pop_front();
    }

    cout << res;
    return 0;
}

Prefix Sum Array Implementation

C++

int main()
{
    int n = readInt();
    int k = readInt();

    vector<ll> a(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        a[i] = a[i - 1] + readInt();

    ll res = a[k];
    for (int i = k + 1; i <= n; ++i)
        res = max(res, a[i] - a[i - k]);

    cout << res;
    return 0;
}

5 bình luận nữa