Problem statement

https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

Solution

What is asked in this problem: we need to take some numbers and some numbers from the beginning, such that the sum of therse taken k numbers are maximal. It is equivalent to take n - k adjacent numbers with minimal sum and then return sum of all numbers minus this value. So, all we need to do is:

  1. Keep wind sum in the window of size n - k.
  2. Move start and end of this window to the right and update wind. Note, that here we have fixed size of our window, so it is very easy.
  3. Update ans on each step: ans = min(ans, wind).
  4. Finally, just return S - ans.

Complexity

Time complexity is just O(n), we iterate evaluate sums and then use sliding window, where we move only to the right. Note, that when evaluated S and ans we can do it in more optimal way, but it will not change the complexity. Space complexity is O(1).

Code

class Solution:
    def maxScore(self, A, k):
        n, S = len(A), sum(A)
        ans = wind = sum(A[:n-k])
        for i in range(n-k, n):
            wind = wind - A[i-n+k] + A[i]
            ans = min(ans, wind)
        
        return S - ans