Maximum Points from Cards

There are n cards arranged in a row, each with a point value. You must pick exactly k cards in total, and on each pick you may take either the card currently at the front of the row or the card currently at the back of the row. Find the maximum total number of points you can collect.

Input: The first line contains two space-separated integers n and k. The second line contains n space-separated integers representing the point value of each card, in row order. Output: Print a single integer: the maximum total points obtainable by taking exactly k cards from either end.

1 <= k <= n <= 10^5 1 <= arr[i] <= 10^4

This is a great example of REFRAMING a problem's OWN NEGATIVE (what's left OUT) rather than tackling its stated POSITIVE (what's taken) directly - a broadly useful problem-solving technique whenever the 'taken' side seems more complex to reason about than its complement.

Pick exactly k cards from either end of a row to maximize their total points. Brute force: Try every possible combination of taking cards from the front and back (all possible splits of k between front-count and back-count) directly, computing the sum for each - this costs O(k²) or requires prefix sums per split, more complex than the equivalent 'minimize the left-out block' reformulation. Optimised: Reframing 'maximize the k cards taken from both ends' as 'minimize the (n-k)-card contiguous block left in the middle' converts a two-ended selection problem into a simple FIXED-SIZE sliding window minimum-sum problem - a much cleaner and more directly solvable formulation.

1. Recognize that taking k cards from the two ends is EQUIVALENT to leaving behind one CONTIGUOUS block of (n-k) cards in the middle. 2. To MAXIMIZE the points taken, MINIMIZE the sum of the contiguous block of size (n-k) left behind. 3. Slide a fixed-size window of length (n-k) across the array to find its MINIMUM sum in O(n), then subtract that from the total sum of all cards.

Time: O(n) - computing the total sum once, then a single sliding window pass to find the minimum block sum. Space: O(1) - a running sum and a running minimum.

Handle k = n (every card must be taken, so the answer is the sum of all cards) and k = 1 (take whichever end card is larger).

Be ready to explain the reformulation trick explicitly - recognizing that 'best selection from both ends' is equivalent to 'worst contiguous block left out' is the single insight that makes this problem tractable with a simple sliding window instead of a more complex two-ended search.