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

Sangnguyen • 4:59 p.m. 15 Tháng 3, 2025 •

include<bits/stdc++.h>

define endl '\n'

typedef long long ll;
using namespace std;

int main() {
ll n,i,k;cin>>n;cin>>k;
ll a[n+1];
ll kq=0;
for(i=1;i<=n;i++){
cin>>a[i];
}
vector<ll> f(n+1);
for(i=1;i<=n;i++){
f[i]=f[i-1]+a[i];
}
for(i=k;i<=n;i++){
kq=max(kq,f[i]-f[i-k]);
}
cout<<kq;
return 0;
}

0
Phản hồi Chia sẻ

leminhduc • 7:42 p.m. 13 Tháng 12, 2024 •

include<bits/stdc++.h>

define ll long long

define f(i, a, b) for(ll i=(a); i<=(b); ++i)

using namespace std;
int main (){
cin.tie(nullptr)->sync_with_stdio(false);
ll n, k, ans=0;
cin >> n >> k;
vector<ll> s(n+1);
s[0]=0;
f(i, 1, n){
ll x;
cin >> x;
s[i]=s[i-1]+x;
}
f(i, 1, n-k+1) ans=max(ans, s[i+k-1]-s[i-1]);
cout << ans;
return 0;
}

0
Phản hồi Chia sẻ

IPHONENEVERDIE • 11:17 a.m. 10 Tháng 12, 2024 •

Dùng Sliding Window nhe

0
Phản hồi Chia sẻ

xuankien18062013 • 7:49 p.m. 21 Tháng 10, 2024 •

N, K = map(int, input().split())
arr = list(map(int, input().split()))
a = sum(arr[:K])
b = a

for i in range(K, N):
a += arr[i]-arr[i -K]
b=max(b, a)

print(b)

1
Phản hồi Chia sẻ

BestFlo2k9 • 12:10 p.m. 26 Tháng 7, 2024 •

Prefix sum là full ac

-1
Phản hồi Chia sẻ

trieuanhtri • 10:23 a.m. 26 Tháng 7, 2024 •
def max_sum_of_k_consecutive_elements(N, K, arr):

current_sum = sum(arr[:K]) max_sum = current_sum for i in range(K, N): current_sum = current_sum - arr[i - K] + arr[i] if current_sum > max_sum: max_sum = current_sum return max_sum

N, K = map(int, input().split())
arr = list(map(int, input().split()))

result = max_sum_of_k_consecutive_elements(N, K, arr)
print(result)
code python full ac nhé
-3
Phản hồi Chia sẻ

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

Phản hồi

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

0
Phản hồi Chia sẻ