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

0

hjhjhjhjhj 3:14 p.m. 6 Tháng 4, 2024

INF = float("-inf")
n, k = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * (n + 1)
for i in range(1, n + 1):
d[i] = d[i - 1] + a[i - 1]
nmax = INF
if k <= n:
for i in range(k, n + 1):
nmax = max(nmax, d[i] - d[i - k])
print(nmax)
PY3

-2

khoinguyentl2023 11:57 a.m. 27 Tháng 3, 2023

admin ơi tăng thời gian cho python đi

1 phản hồi

4

Phucc 9:48 p.m. 5 Tháng 10, 2022

ad ơi ad cập nhật tăng bộ nhớ đi ạ, em làm đúng kết quả nhưng thiếu bộ nhớ :((

1 phản hồi

-42

donhatnam 9:24 a.m. 1 Tháng 9, 2020

Đề bài bảo: Cho dãy số nguyên dương gồm N phần tử a1,a2,...,aN và số nguyên 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ị lớn nhất đó.

Dữ liệu:

Dòng đầu tiên gồm hai số nguyên dương N và K (K≤N≤105);
N dòng sau, mỗi dòng gồm một số nguyên dương: a1,a2,...,aN(ai≤109).
Kết quả:

In ra tổng lớn nhất của K phần tử liên tiếp.

Mà đâu có thấy n dòng nào đâu

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

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;
}

0

SPyofgame 3:39 p.m. 7 Tháng 6, 2020

Tag: Sliding window || Prefix Sum Array