Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Whatever you take, the cards you leave are a contiguous block of n − k cards.
  2. 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