LeetMotion
There are several cards arranged in a row, and each card has an associated number of points given in the integer array cardPoints.
In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.
Your score is the sum of the points of the cards you have taken. Return the maximum score you can obtain.
n-k cards form a contiguous subarray in the middle. So instead of thinking about which cards to take, think about which n-k cards to leave behind.score = totalSum - (sum of middle cards), maximizing the score is equivalent to minimizing the sum of the n-k middle cards. This transforms the problem into: find the minimum sum subarray of fixed length n-k.windowSize = n-k. Compute the initial window sum, then slide right one element at a time: windowSum += cardPoints[r], windowSum -= cardPoints[r - windowSize]. Track the minimum window sum seen. Answer = totalSum - minWindowSum.You have a time-ordered list of stocks and you can sell exactly k of them — but only from the beginning or end of the list (oldest or newest trades). You want to maximize total value. The key insight: whatever you sell, you leave a contiguous block in the middle untouched. So find the middle block whose value is smallest, and sell everything else. The sliding window locates that minimum-value middle block in O(n).
The core insight: any selection of k cards from both ends leaves exactly n-k cards as a contiguous middle block. So maximizing the score = minimizing the middle block sum. Slide a fixed window of size n-k across the array, tracking the minimum sum. Answer = totalSum - minWindowSum.
totalSum and windowSize = n - k. If windowSize == 0, return totalSum.windowSum = sum(cardPoints[:windowSize]). Set minWindowSum = windowSum.i = windowSize to n-1: add cardPoints[i], subtract cardPoints[i-windowSize]. Update minWindowSum.totalSum - minWindowSum.The visualization highlights cards you take (green) vs the middle window you leave (red/dim). When a new minimum window is found, the selected cards flash brightly.
Discussion
…