Practice › Sliding Window
Maximum Points from Cards
Medium · Sliding Window · Asked at Google, Amazon, Microsoft
Cards lie in a row with points a[i]. In each step you take one card from the beginning or the end of the row. You must take exactly k cards. Print the maximum total points.
Input
First line: n k. Second line: n integers.
Output
The maximum score.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^4
You take i cards from the left and k − i from the right. Equivalently, the n − k cards you leave form a contiguous window with minimum sum.
Example 1
Input
7 3 1 2 3 4 5 6 1
Output
12
Example 2
Input
3 3 9 7 7
Output
23
Hints
- Whatever you take, the cards you leave are a contiguous block of n − k cards.
- Maximising what you take = minimising the sum of that block. Or: try i cards from the left and k − i from the right with prefix sums.
Approach
Start by taking the first k cards. Then, k times, give back the last card taken from the left and take one more from the right end, updating the sum in O(1) and keeping the maximum. That checks every split (i from the left, k − i from the right).
Complexity: O(k) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long cur = 0;
for (int i = 0; i < k; i++) cur += a[i];
long long best = cur;
for (int i = 1; i <= k; i++) {
cur += a[n - i] - a[k - i];
best = max(best, cur);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
cur = sum(a[:k])
best = cur
for i in range(1, k + 1):
cur += a[n - i] - a[k - i]
best = max(best, cur)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long cur = 0;
for (int i = 0; i < k; i++) cur += a[i];
long best = cur;
for (int i = 1; i <= k; i++) {
cur += a[n - i] - a[k - i];
best = Math.max(best, cur);
}
System.out.println(best);
}
}Solve Maximum Points from Cards online · All practice problems