There are several cards arranged in a row, and each card has an associated number of points The points are 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.
Given the integer array cardPoints and the integer k, return the maximum score you can obtain.
 
Example 1:
Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:
Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:
Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:
Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:
Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

 
Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Difficulty: interview

Starter code:

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        

Solutions:
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        max_score = 0
        curr_score= 0
        init_hand = cardPoints[len(cardPoints)-k:]
        max_score = sum(init_hand)
        curr_score = max_score
        for i in range(k):
            curr_score -= init_hand[i]
            curr_score += cardPoints[i]
            if curr_score > max_score:
                max_score = curr_score
        return max_score

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        min = 0
        window = 0
        all = 0
        for i in range(n):
            window += cardPoints[i]
            all += cardPoints[i]
        min = window
        # print(all)

        for x in range(k):
            # print(x)
            all += cardPoints[x+n]
            window -= cardPoints[x]
            window += cardPoints[x+n]
            if window < min:
                min = window
        return all - min
        # print(all)
        # print(all-min)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        result = curr = 0
        for i in range(-k, k):
            curr += cardPoints[i]
            if i >= 0:
                curr -= cardPoints[i - k]
            result = max(result, curr)
        return result

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # dfs TLE
        # use sliding window instead
        # keep moving a window of size n - k along the way
        
        maxSum = sum(cardPoints)
        if len(cardPoints) <= k:
            return maxSum
        
        subSum = 0
        ans = 0
        for i in range(len(cardPoints)):
            subSum += cardPoints[i]
            
            if i + 1 >= (len(cardPoints) - k):
                ans = max(ans, maxSum - subSum)
                subSum -= cardPoints[i - (len(cardPoints) - k - 1)]
        
        return ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        answer = 0
        left = [0]*len(cardPoints)
        right = [0]*len(cardPoints)
        
        for i in range(len(cardPoints)) :
            if i == 0 : left[0] = cardPoints[0]
            else :
                left[i] = left[i-1] + cardPoints[i]
        
        for i in range(len(cardPoints)-1,-1,-1) :
            if i == len(cardPoints)-1 : right[-1] = cardPoints[-1]
            else :
                right[i] = right[i+1] + cardPoints[i]
        
        for i in range(k+1) :
            if i == 0 : Sum = right[-k]
            elif i == k : Sum = left[k-1]
            else : 
                Sum = left[k-i-1] + right[-i]
            answer = max(answer,Sum)
        return answer                

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        size = len(cardPoints) - k
        minSum = float('inf')
        cur = 0
        left = 0
        
        for i, v in enumerate(cardPoints):
            cur += v
            if i - left + 1 > size:
                cur -= cardPoints[left]
                left += 1
            if i - left + 1 == size:
                minSum = min(minSum, cur)
                
        return sum(cardPoints) - minSum
        
            


class Solution:
    def maxScore(self, points: List[int], num_cards: int) -> int:
        size = len(points) - num_cards
        min_subarray_sum = math.inf
        left = curr = 0
        for right, val in enumerate(points):
            curr += val
            if right - left + 1 > size:
                curr -= points[left]
                left += 1
            if right - left + 1 == size:
                min_subarray_sum = min(min_subarray_sum, curr)
        return sum(points) - min_subarray_sum

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        min = 0
        window = 0
        all = 0
        for i in range(n):
            window += cardPoints[i]
            all += cardPoints[i]
        min = window
        # print(all)

        for x in range(k):
            # print(x)
            y = x+n
            all += cardPoints[y]
            window -= cardPoints[x]
            window += cardPoints[y]
            if window < min:
                min = window
        return all - min
        # print(all)
        # print(all-min)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # The Edge Case not needed here: if k > len(cardPoints) or k<=0: raise ValueErro('')
        left, right = [0], [0]
        for i in range(k):
            left.append(left[-1]+ cardPoints[i])
            right.append(right[-1] + cardPoints[len(cardPoints) -1 - i])
        
        res  = 0 
        for i in range(k+1):
            
            x = left[i] + right[k-i]
            res = max(res,x)
            
        return res


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # The Edge Case not needed here: if k > len(cardPoints) or k<=0: raise ValueErro('')
        # Your solution is O(N) and this solution is O(k)
        # Eventhough the real time is similar, O(k) is better
        left = [0] * (k+1)
        right = [0] * (k+1)
        for i in range(k):
            left[i+1] = left[i] + cardPoints[i]
            right[i+1] = right[i] + cardPoints[-i-1]
        return max(left[j]+right[k-j] for j in range(k+1))

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:        
        left_cumsum = [0]
        right_cumsum = [0]
        for p in cardPoints[:k+1]:
            left_cumsum.append(left_cumsum[-1] + p)
        for p in reversed(cardPoints[-(k+1):]):
            right_cumsum.append(right_cumsum[-1] + p)
        
        result = 0
        for i in range(k+1):
            result = max(result, left_cumsum[i] + right_cumsum[k-i])
        return result

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left, right = [0], [0]
        for i in range(len(cardPoints)):
            left.append(left[-1]+cardPoints[i])
            right.append(right[-1]+cardPoints[-i-1])
        return max(left[i]+right[k-i] for i in range(k+1))

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        n = len(cardPoints)
        
        # prefix sum solution
        pre = [0]*(n+1)
        for i in range(n):
            pre[i+1] = pre[i] + cardPoints[i]
            
        max_val = -1
        
        for i in range(k+1):
            max_val = max(max_val, pre[i] + pre[n] - pre[n-k+i])
            
        return max_val
        
#         if k >= n:
#             return sum(cardPoints)
        
#         def dfs(i,j):
#             if i + (n-j-1) >= k:
#                 return 0
            
#             else:
#                 return max(dfs(i+1,j)+cardPoints[i], dfs(i,j-1)+cardPoints[j])
            
#         return dfs(0,n-1)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        total = sum(cardPoints)
        if n == k or n < k : return total 
        remove = n - k
        ans = 0
        
        '''memo = [0]*(n+1)
        memo[0] = 0
        
        start = 0
        for i in range(0, n):
            memo[i+1] = memo[i] + cardPoints[i]            
            if i-start + 1 == remove: 
                ans = max(ans, total-(memo[i+1]-memo[start]))
                start = start+1'''
        curr = 0
        start = 0
        for right in range(n):
            curr += cardPoints[right]
            if right-start+1 == remove:
                ans = max(ans, total-curr)
                curr -= cardPoints[start]
                start +=1
            
            
        return ans

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left, right = [0], [0]
        for i in range(k):
            left.append(left[-1]+ cardPoints[i])
            right.append(right[-1] + cardPoints[len(cardPoints) -1 - i])
        
        res  = 0 
        for i in range(k+1):
            
            x = left[i] + right[k-i]
            res = max(res,x)
            
        return res
            

#         front_sum=back_sum=[0]
#                 print 'cardPoints:', cardPoints
#         print 'k:', k
#         frontSum, backSum = [0], [0]
#         for n in cardPoints:
#             frontSum.append(frontSum[-1]+n)
#             print 'frontSum:', frontSum
#         for n in cardPoints[::-1]:
#             backSum.append(backSum[-1]+n)
#             print 'backSum:', backSum
#         allCombinations = [frontSum[i]+backSum[k-i] for i in range(k+1)]
#         print 'allCombinations:', allCombinations
#         return max(allCombinations)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        min_len = len(cardPoints) - k
        curr_sum = 0
        min_val = 0
        for start in range(len(cardPoints) - min_len + 1):
            if start == 0:
                curr_sum = sum(cardPoints[start:start+min_len])
                min_val = curr_sum
            else:
                curr_sum = curr_sum - cardPoints[start - 1] + cardPoints[start+min_len-1] 
                if min_val > curr_sum:
                    min_val = curr_sum
        
        return sum(cardPoints) - min_val
            

#         front_sum=back_sum=[0]
#                 print 'cardPoints:', cardPoints
#         print 'k:', k
#         frontSum, backSum = [0], [0]
#         for n in cardPoints:
#             frontSum.append(frontSum[-1]+n)
#             print 'frontSum:', frontSum
#         for n in cardPoints[::-1]:
#             backSum.append(backSum[-1]+n)
#             print 'backSum:', backSum
#         allCombinations = [frontSum[i]+backSum[k-i] for i in range(k+1)]
#         print 'allCombinations:', allCombinations
#         return max(allCombinations)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        min = 0
        window = 0
        all = 0
        for i in range(n):
            window += cardPoints[i]
            all += cardPoints[i]
        min = window
        print(all)

        for x in range(k):
            print(x)
            all += cardPoints[x+n]
            window -= cardPoints[x]
            window += cardPoints[x+n]
            if window < min:
                min = window
        return all - min
        # print(all)
        # print(all-min)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        sums = [0] * (n+1)
        for i in range(1, n+1):
            sums[i] = sums[i-1] + cardPoints[i-1]
            
        ans = float('inf')
        for i in range(k+1):
            ans = min(ans, sums[i+n-k] - sums[i])
        
        print((sums, ans))
        return sums[-1] - ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        s = sum(cardPoints)
        if k >= len(cardPoints):
            return s
        maxPoint = 0
        cur = 0
        j = 0
        # i-j+k == n
        n = len(cardPoints)
        for i, point in enumerate(cardPoints):
            if i-j+k > n-1:
                cur -= cardPoints[j]
                j += 1
            cur += point
            if i-j+k == n-1:
                maxPoint = max(maxPoint, s-cur)
        return maxPoint


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # find a subarray in the middle that its sum is min, maintain n-k length
        n = len(cardPoints)
        runningsum = 0
        start = end = 0
        total = sum(cardPoints)
        minsum = float('inf')
        while end < len(cardPoints):
          runningsum += cardPoints[end]
          if end - start + 1 > n-k:
            runningsum -= cardPoints[start]
            start += 1
          if end - start + 1 == n-k:
            minsum = min(minsum, runningsum)
          end += 1
        return total-minsum


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
#         cardLen = len(cardPoints)
#         if cardLen == k:
#             return sum(cardPoints)
        
#         dp = {}
#         def takeCard(l0, r0, k0):
#             if k0 == 1:
#                 return max(cardPoints[l0], cardPoints[r0])
#             if (l0, r0, k0) in dp:
#                 return dp[(l0, r0, k0)]
            
#             ans = max(cardPoints[l0] + takeCard(l0+1, r0, k0-1), cardPoints[r0] + takeCard(l0, r0-1, k0-1))
#             dp[(l0, r0, k0)] = ans
            
#             return ans
        
#         return takeCard(0, cardLen-1, k)
        cardLen = len(cardPoints)
        frontSum = [0]
        for num in cardPoints:
            frontSum.append(frontSum[-1]+ num)
        backSum = [0 for _ in range(cardLen + 1)]
        for i in range(cardLen - 1, -1, -1):
            backSum[i] = cardPoints[i] + backSum[i+1]
        ans = frontSum[k]
        for i in range(k):
            ans = max(ans, frontSum[i] + backSum[-(k-i)-1])
        return ans

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left, right = [0], [0]
        for i in range(k):
            left.append(left[-1]+ cardPoints[i])
            right.append(right[-1] + cardPoints[len(cardPoints) -1 - i])
        print(left)
        print(right)
        res  = 0 
        for i in range(k+1):
            
            x = left[i] + right[k-i]
            res = max(res,x)
            
        return res
            
            
        


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        forwardSum = [m for m in cardPoints]
        backwardSum = cardPoints.copy()
        backwardSum.append(0)
        for c in range(1, len(cardPoints)):
            forwardSum[c] = forwardSum[c-1] + forwardSum[c]
        
        for l in range(len(cardPoints)-2, 0, -1):
            backwardSum[l] = backwardSum[l+1] + backwardSum[l]
        maximum = 0
        for i in range(k-1, -2, -1):
            if i != -1:
                maximum = max(maximum, forwardSum[i] + backwardSum[len(backwardSum)-1-(k-1-i)])
            else:
                maximum = max(maximum, backwardSum[len(backwardSum)-1-k])
                              
        return maximum


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        min = 0
        window = 0
        all = 0
        for i in range(n):
            window += cardPoints[i]
        min = window
        all = window
        # print(all)

        for x in range(k):
            # print(x)
            all += cardPoints[x+n]
            window -= cardPoints[x]
            window += cardPoints[x+n]
            if window < min:
                min = window
        return all - min
        # print(all)
        # print(all-min)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        score = sum(cardPoints[:k])
        best = score
        
        for i in range(k):
            score += cardPoints[-(i+1)] - cardPoints[k-i-1]
            if score > best:
                best = score
            
        return best

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        leftsum = [0] * len(cardPoints)
        rightsum = [0] * len(cardPoints)
        n = len(cardPoints)
        leftsum[0] = cardPoints[0]
        rightsum[n-1] = cardPoints[n-1]
        for i in range(1,n):
            leftsum[i] = leftsum[i-1] + cardPoints[i]
            rightsum[n-1-i] = rightsum[n-1-i+1] + cardPoints[n-1-i]
            
        res = max(leftsum[k-1],rightsum[-(k-1+1)])

        
        for i in range(k-1):
            
            res = max((leftsum[i] + rightsum[-(k-i-1)]), res)
            
        return res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        '''
        convert this into a sliding window problem
        rephrase the problem:
            find the max window of length k between cardPoints[n-k:n+k]
        [1,2,3,4,5,6]
        k = 2
        4,5,0,1
        
            
        '''
        ans = 0
        curSum = 0
        n = len(cardPoints)
        for i in range(n-k, n+k):
            curSum += cardPoints[i%n]
            if i >= n:
                curSum -= cardPoints[(i-k)%n]
            ans = max(ans, curSum)
        return ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if not cardPoints or len(cardPoints) == 0:
            return 0
        window = len(cardPoints) - k
        res = float('inf')
        s = 0
        for i in range(window):
            s += cardPoints[i]
        res = min(s, res)
        for i in range(window, len(cardPoints)):
            print(cardPoints[i],s,i)
            s -= cardPoints[i-window]
            s += cardPoints[i]
            res = min(s, res)
        return sum(cardPoints) - res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        n = len(cardPoints)
        if n == k:
            return sum(cardPoints)
        
        pre, post = [0] * (n + 1), [0] * (n + 1)
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + cardPoints[i - 1]
        for i in range(1, n + 1):
            post[i] = post[i - 1] + cardPoints[n - i]
            
        best = 0
        
        # n = 7
        # k = 3
        # i = 0
        # x = 5
        # print (pre, post)
        for i in range(k + 1):
            best = max(best, pre[i] + post[k - i])
        
        return best

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if k == len(cardPoints):
            return sum(cardPoints)
        front = [0] * k
        back = [0] * k
        front[0] = cardPoints[0]
        for i in range(1,k):
            front[i] = front[i-1] + cardPoints[i]
            
        back[0] = cardPoints[-1]
        for i in range(1,k):
            back[i] = back[i-1] + cardPoints[-1-i]
        
        max_score = 0
        print(front,back)
        for i in range(k+1):
            if i == 0:
                max_score = max(max_score,back[-1])
                # print(i,back[-1])
            elif i == k:
                max_score = max(max_score,front[k-1])
                # print(i,front[k-1])
            else:
                max_score = max(max_score,front[i-1]+back[k-i-1])
                # print(i,k-i,max_score,front[i-1]+back[k-i-1])
            # print(i,k-i,max_score)
        return max_score

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        length = len(cardPoints)
        total = sum(cardPoints)
        if k == length:
            return total
        curr = 0
        temp = 2 ** 31 - 1
        left = 0
        for right in range(length):
            curr += cardPoints[right]
            if right - left + 1 < length - k:
                continue
            print(right, curr)
            temp = min(temp, curr)
            curr -= cardPoints[left]
            left += 1
        
        return total - temp

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        
        cum_sum = [0 for i in range(n)]
        cum_sum[0] = cardPoints[0]
        rev_sum = [0 for i in range(n)]
        rev_sum[0] = cardPoints[-1]
        
        
        for i in range(1,n):
            cum_sum[i] = cum_sum[i-1]+cardPoints[i]
            rev_sum[i] = rev_sum[i-1]+cardPoints[n-i-1]
            
        max_sum = max(cum_sum[k-1],rev_sum[k-1])
        
        for i in range(1,k):
            max_sum = max(max_sum,(cum_sum[i-1]+rev_sum[k-i-1]))
            
        return max_sum


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        remainCnt = len(cardPoints) - k
        if remainCnt == 0: return sum(cardPoints)
        minRemainSum = float('inf')
        curr = 0
        cnt = 0
        for i in range(len(cardPoints)):
            cnt += 1
            curr += cardPoints[i]
            if cnt == remainCnt:
                minRemainSum = min(minRemainSum, curr)
                curr -= cardPoints[i + 1 - cnt]
                cnt -= 1
        
        return sum(cardPoints) - minRemainSum


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # Sliding window of length k
        ans = total = sum(cardPoints[:k])
        for i in range(1, k+1):
            total -= cardPoints[k-i]
            total += cardPoints[-1-i+1]
            ans = max(ans, total)
        return ans


from collections import deque
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        first = deque(cardPoints[0:k])
        second = deque(cardPoints[len(cardPoints)-k:])
        final = 0
        
        firstSum = sum(first)
        secondSum = sum(second)
        
        for i in range(k):
            if firstSum > secondSum:
                final += first[0]
                firstSum -= first.popleft()
                secondSum -= second.popleft()
                
            else:
                final += second[len(second)-1]
                firstSum -= first.pop()
                secondSum -= second.pop()

        return final

class Solution:
    def maxScore(self, cardPoints, k: int) -> int:
        N = len(cardPoints)
        preS, afterS = [0]*(N+1), [0]*(N+1)
        ans = 0
        for i in range(1,N+1):
            preS[i]=preS[i-1]+cardPoints[i-1]
        for j in range(1,N+1):
            afterS[j] = afterS[j-1]+cardPoints[N-j]
        for l in range(k+1):
            ans = max(ans,preS[l]+afterS[k-l])
        return ans

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        right_index = len(cardPoints)-k
        curr_max = sum(cardPoints[right_index:])
        curr_sum = curr_max
        for left_index in range(0, k):
            curr_sum -= cardPoints[right_index]
            right_index += 1
            curr_sum += cardPoints[left_index]
            if curr_sum > curr_max:
                curr_max = curr_sum
        return curr_max


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        n = len(cardPoints)
        
        cum_sum = [0 for i in range(n)]
        cum_sum[0] = cardPoints[0]
        rev_sum = [0 for i in range(n)]
        rev_sum[0] = cardPoints[-1]
        
        
        for i in range(1,n):
            cum_sum[i] = cum_sum[i-1]+cardPoints[i]
            rev_sum[i] = rev_sum[i-1]+cardPoints[n-i-1]
            
        max_sum = max(cum_sum[k-1],rev_sum[k-1])
        
        for i in range(1,k):
            max_sum = max(max_sum,(cum_sum[i-1]+rev_sum[k-i-1]))
        
        return max_sum

class Solution:
    def maxScore(self, A: List[int], k: int) -> int:    
        su = sum(A[:k])
        n = len(A) 
        res = su   
        for i in range(k):
            su -= A[k-i-1]
            su += A[n-i-1]
            res = max(res, su) 
        return res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # sum of points from left most
        # sum of points from right most
        # sum of points from both left and right
        
        # defualt max_sum
        total = sum(cardPoints[:k])
            
        # if k == len(cardPoitns), result is the total sum of cardPoints
        if k == len(cardPoints):
            return total
        max_sum = total
        print(max_sum)
        
        # compute sum from left to right
        for i in range(k - 1, -1, -1):
            total = total + cardPoints[i - k] - cardPoints[i]
            print((i-k, total, cardPoints[i - k], cardPoints[i]))
            if total > max_sum:
                max_sum = total
        return max_sum


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        j = len(cardPoints) - 1
        ms = 0
        
        for i in range(k):
            ms += cardPoints[j]
            j -= 1
            
        cand = ms
        
        for i in range(k):
            cand += cardPoints[i] - cardPoints[j+1]
            j += 1
            ms = max(cand, ms)
            
        return ms

class Solution:
    def maxScore(self, nums: List[int], k: int) -> int:
        
        n = len(nums)

        if k == n:
            return sum(nums)
        
        pre =[0]
        post = []
        
        for e in nums:
            pre.append(pre[-1]+e)
            post.append(e)
        post.append(0)
        
        
        for i in range(n-1,-1,-1):
            post[i] = post[i+1] + nums[i]
            
        res = 0
        j = n - k
        
        while j <= n:
            res = max(res, pre[i] + post[j])
            
            i+=1
            j+=1
            
        return res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if len(cardPoints) < k:
            return -1
        
        remain = len(cardPoints) - k
        suum = sum(cardPoints[:remain])
        min_suum = suum
        for i in range(remain, len(cardPoints)):
            suum = suum - cardPoints[i-remain] + cardPoints[i]
            min_suum = min(min_suum, suum)
        return sum(cardPoints) - min_suum

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        sums = [0] * (n+1)
        for i in range(1, n+1):
            sums[i] = sums[i-1] + cardPoints[i-1]
            
        ans = float('inf')
        for i in range(k+1):
            ans = min(ans, sums[i+n-k] - sums[i])
        
        return sums[-1] - ans


class Solution:
    def maxScore(self, A: List[int], k: int) -> int:    
        su = sum(A[:k])
        res = su   
        for i in range(k):
            su -= A[k-i-1]
            su += A[len(A)-i-1]
            res = max(res, su) 
        return res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        l, r, res, count = 0, 0, sum(cardPoints[:n]), 0
        while r < len(cardPoints):
            count += cardPoints[r]
            if r >= n:
                count -= cardPoints[l]
                l += 1
                res = min(res, count)
            r += 1
        return sum(cardPoints) - res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        pre = [cardPoints[0]]
        n = len(cardPoints)
        for i in range(1, n):
            pre.append(pre[-1] + cardPoints[i])
        
        if k == n:
            return pre[-1]
        
        s = pre[-1]
        cur_s = pre[n - k - 1]
        l = 0
        r = n - k + l - 1
        ans = s - pre[n - k - 1]
        
        while l != len(cardPoints) - (n - k) :
            cur_s -= cardPoints[l]
            l += 1
            r += 1
            cur_s += cardPoints[r]
            ans = max(ans, s - cur_s)
            
        return ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints) - k
        current = 0
        for i in range(n):
            current += cardPoints[i]
        result = current
        
        for i in range(1, k+1):
            current -= cardPoints[i-1]
            current += cardPoints[i+n-1]
            result = min(result, current)
        
        return sum(cardPoints) - result
        


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        f, b = [0], [0]
        for n in cardPoints:
            f.append(f[-1] + n)
        for n in cardPoints[::-1]:
            b.append(b[-1] + n)
        allCombo = [f[i] + b[k-i] for i in range(k+1)]
        return max(allCombo)


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        points_L = []
        points_R = []
        
        for p in cardPoints:
            if len(points_L): points_L.append(points_L[-1] + p)
            else: points_L.append(p)
        for p in cardPoints[::-1]:
            if len(points_R): points_R.append(points_R[-1] + p)
            else: points_R.append(p)
        points_R = points_R[::-1]
            
        return self.solution(points_L, points_R, k)
    

    def solution(self, points_L, points_R, k):
        max = 0
        for i in range(k+1):
            cmp1 = points_L[i-1] if i > 0 else 0
            cmp2 = points_R[-(k-i)] if i < k else 0
            score = cmp1 + cmp2
            if score > max:
                max = score
        return max


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left_sums = [0] * (k + 1)
        right_sums = [0] * (k + 1)
        
        
        for i in range(k):
            left_sums[i+1] = left_sums[i] + cardPoints[i]
            right_sums[i+1] = right_sums[i] + cardPoints[len(cardPoints)-i-1]
        

        res = 0
        for i in range(k+1): # we must include K as a choice
            j = k-i
            res = max(res, left_sums[i] + right_sums[j])
        
        return res


from functools import lru_cache
import sys
from itertools import accumulate

sys.setrecursionlimit(10**5)


class Solution:
    def maxScore(self, arr: List[int], k: int) -> int:

        n = len(arr)
        pre = list(accumulate(arr))
        total = pre[-1]
        # print(f'{pre=}')
        
        if k == n:
            return total
        
        w = n-k
        result = 0 
        # print(f'{w=}')
        
        for i in range(w-1, n):
            # print(f'{i=}')
            sub_sum = total - (pre[i] - pre[i-w+1] + arr[i-w+1])
            result = max(result, sub_sum)
            
            
        return result

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        curr_max = sum(cardPoints[0:k])
        curr_sum = curr_max
        for i in range(1, k+1):
            curr_sum = curr_sum - cardPoints[k-i] + cardPoints[-i]
            curr_max = max(curr_max, curr_sum)
        return curr_max


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        size = len(cardPoints)
        maxRightSum = sum(cardPoints[size-k:])
        ans = maxRightSum
        currSum = maxRightSum
        # sum with left
        for i in range(k):
            currSum = currSum - cardPoints[size-k+i] + cardPoints[i]
            ans = max(ans, currSum)
        return ans
    # def maxScore(self, cardPoints: List[int], k: int) -> int:
    #     windowEnd = 0
    #     size = len(cardPoints) - k
    #     ans = float(\"inf\")
    #     currSum = 0
    #     for windowStart, point in enumerate(cardPoints):
    #         currSum += point
    #         if windowStart - windowEnd + 1 > size:
    #             currSum -= cardPoints[windowEnd]
    #             windowEnd += 1
    #         if windowStart - windowEnd + 1 == size:
    #             ans = min(ans, currSum)
    #     return sum(cardPoints) - ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        curr_max = sum(cardPoints[0:k])
        curr_sum = curr_max
        for i in range(1, k+1):
            curr_sum = curr_sum - cardPoints[k-i] + cardPoints[-i]
            curr_max = max(curr_max, curr_sum)
        return curr_max


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        totalPoints, window = sum(cardPoints), len(cardPoints) - k
        i, j, Sum, Min = 0, 0, 0, totalPoints
        
        while j < len(cardPoints):
            Sum += cardPoints[j]
            
            if j - i + 1 > window:
                Sum -= cardPoints[i]
                i += 1
            
            if j - i + 1 == window: Min = min(Min, Sum)
            j += 1
        
        # print(Min)
        return totalPoints - Min
        
        
        


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if len(cardPoints) < k:
            return 0
        if len(cardPoints) == k:
            return sum(cardPoints)
        n = len(cardPoints)
        res, cur = sum(cardPoints[:k]), sum(cardPoints[:k])
        for i in range(k):
            cur += cardPoints[n-i-1]-cardPoints[k-1-i]
            res = max(res, cur)
        return res

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if not cardPoints or k==0:
            return 0
        for i in range(1,len(cardPoints)):
            cardPoints[i]+=cardPoints[i-1]
            
        if k==len(cardPoints):
            return cardPoints[-1]
        ans=cardPoints[k-1]
        
        for i in range(1,k+1):
            print(i)
            ans=max(ans,cardPoints[k-i]+cardPoints[-1]-cardPoints[-i])
            print(cardPoints[k-i],cardPoints[-1]-cardPoints[-i])
        return max(ans,cardPoints[-1]-cardPoints[-(k+1)])

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        left = n - k
        mini = sum(cardPoints[:left])
        cur = mini
        for i in range(left, n):
            cur = cur - cardPoints[i-left] + cardPoints[i]
            mini = min(mini, cur)
        
        return sum(cardPoints) - mini

class Solution:
    def maxScore(self, card_points: List[int], k: int) -> int:
        window_size = len(card_points) - k
        current_min_sum, min_sum = 0, sys.maxsize
        total_points = 0
        left = 0
        for right, value in enumerate(card_points):
            total_points += value
            current_min_sum += value

            current_size = right - left + 1
            if current_size < window_size:
                continue

            if current_size > window_size:
                current_min_sum -= card_points[left]
                left += 1

            min_sum = min(min_sum, current_min_sum)

        return total_points - min_sum


def max_score_using_subsequence(card_points, k):
    l = len(card_points) - k
    if l == 0:
        return sum(card_points)
    
    sum_subsequence = 0
    for i in range(l):
        sum_subsequence += card_points[i]
    
    lowest = sum_subsequence
    for i in range(len(card_points) - l):
        sum_subsequence = sum_subsequence - card_points[i] + card_points[i+l]
        if sum_subsequence < lowest:
            lowest = sum_subsequence
    
    return sum(card_points) - lowest
    

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # return max_score_recursive(cardPoints, k, 0, len(cardPoints)-1, {})
        return max_score_using_subsequence(cardPoints, k)

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        psum = sum(cardPoints[:k])
        res = psum
        n = len(cardPoints)
        for i in range(k):
            psum += cardPoints[n - i - 1] - cardPoints[k - i - 1]
            res = max(res, psum)
        return res


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        pre_sum = []   # i: sum of all items before i
        temp_left = 0
        for i, v in enumerate(cardPoints):
            pre_sum.append(temp_left)
            temp_left += v
        pre_sum.append(temp_left)
        
        post_sum = []  # i: sum of all items after i-1
        temp_right = 0
        temp_right = 0
        for i in range(len(cardPoints)-1, -1, -1):
            v = cardPoints[i]
            post_sum.append(temp_right)
            temp_right += v
        post_sum.append(v)
        post_sum.reverse()
        # print(pre_sum)
        # print(post_sum)
        return max([pre_sum[i] + post_sum[-(k-i)-1] for i in range(k+1)])
            
            
            



from collections import deque
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        cards = n-k
        minimum = 0
        if (cards != 0):
            sum1 = 0
            q = deque()
            for i in range(cards):
                q.append(cardPoints[i])
                sum1 += cardPoints[i]
            minimum = sum1
            for i in range(cards, n):
                first = q.popleft()
                q.append(cardPoints[i])
                sum1 -=first
                sum1 += cardPoints[i]
                if (sum1 < minimum):
                    minimum = sum1
        #else:
         #   minimum = 0
        print(minimum)
        return sum(cardPoints) - minimum


class Solution:
    def maxScore(self, l: List[int], k: int) -> int:
        length = len(l)
        
        if k == length:
            return sum(l)
        elif k == 0:
            return 0
        
        k = length - k
        v = curr_min = sum(l[:k])
        
        for i in range(k,length):
            v =  v - l[i-k] + l[i]
            curr_min = min(curr_min, v)
        
        return sum(l) - curr_min


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        if k == len(cardPoints):
            return sum(cardPoints)
        size = len(cardPoints) - k
        min_sum = float('inf')
        left = 0
        right = 0
        window_sum = 0
        while right < len(cardPoints):
            window_sum += cardPoints[right]
            right += 1
            while right - left == size:
                min_sum = min(min_sum, window_sum)
                window_sum -= cardPoints[left]
                left += 1
        return sum(cardPoints) - min_sum


class Solution:
    def maxScore(self, p: List[int], k: int) -> int:
        res = sum(p[:k])
        cur = res
        
        for i in range(1, k+1):
            cur += p[-i] - p[k-i]
            res = max(cur, res)
        
        return res


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        # Time: O(k)
        # Space: O(1)
        ans = win = 0
        for i in range(-k, k):
            win += cardPoints[i]
            if i >= 0:
                win -= cardPoints[i - k]
            #print(i, i-k, ans, win, cardPoints[i] )    
            ans = max(win, ans)    
        return ans
        
            


# O(n) time and O(1) space
# alternative dp solution O(k) space: form two k sized arrays: 1 to k and n-k to n
# https://www.youtube.com/watch?v=t3JHx5J01F0 9mins06s
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        curr_max = sum(cardPoints[:k])
        ans = curr_max
        for i in range(1, k+1):
            curr_max += cardPoints[-i] - cardPoints[k-i]
            ans = max(ans, curr_max)
        return ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        w = n - k
        left, right = 0, w - 1
        ans = float('-inf')
        
        win_sum = sum(cardPoints[:w])
        total = sum(cardPoints)
        while right < n:
            sub = total - win_sum
            ans = max(sub, ans)
            if left < n:
                win_sum -= cardPoints[left]
            left += 1
            right += 1
            if right < n:
                win_sum += cardPoints[right]

        return ans


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
#         我写的还是太复杂了
#         if not cardPoints or not k:
#             return 0
#         if k==len(cardPoints):
#             return sum(cardPoints)
        
#         front={0:0}
#         back={0:0}
#         total=0
#         for i in range(k):
#             total+=cardPoints[i]
#             front[i+1]=total
#         total=0
#         for i in range(-1,-k-1,-1):
#             total+=cardPoints[i]
#             back[-i]=total
            
#         maxres=float('-inf')
#         for i in range(k+1):
#             maxres=max(maxres,front[i]+back[k-i])
        
#         return maxres
        s = sum(cardPoints[:k])
        res = s
        for i in range(1, k+1):
            s += cardPoints[-i] - cardPoints[k-i]
            res = max(res, s)
        return res


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left, right = [0], [0]
        for i in range(k):
            left.append(left[-1] + cardPoints[i])
            right.append(right[-1] + cardPoints[len(cardPoints) - 1 - i])
        # print(left, right)
        maxSoFar = 0
        for i in range(k + 1):
            if left[i] + right[k - i] > maxSoFar:
                maxSoFar = left[i] + right[k - i]
        return maxSoFar
        


class Solution:
    def maxScore(self, p: List[int], k: int) -> int:
        s = sum(p)
        if k == len(p): return s
        n = len(p)
        for i in range(1, len(p)): p[i] += p[i-1]

        return s - min(p[n+i-k-1] - (p[i-1] if i else 0) for i in range(k+1))


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        score = 0
        l = k
        prefix = [0]
        for i in range(len(cardPoints)):
            prefix.append(prefix[-1] + cardPoints[i])
        for i in range(k+1):
            score = max(score, prefix[l] + prefix[-1] - prefix[-1-i])
            l -= 1
        return score

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        right_index = len(cardPoints)-k
        curr_max = sum(cardPoints[right_index:])
        curr_sum = curr_max
        for left_index, right_index in zip(list(range(0, k)), list(range(len(cardPoints)-k, len(cardPoints)))):
            print((left_index, right_index))
            curr_sum -= cardPoints[right_index]
            curr_sum += cardPoints[left_index]
            curr_max = max(curr_max, curr_sum)
        return curr_max


class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:  
        sub_len = len(cardPoints) - k
        localSum = 0
        localSum = sum(cardPoints[0: sub_len])
        localMin = localSum
        for i in range(sub_len, len(cardPoints)):
            localSum += cardPoints[i]
            localSum -= cardPoints[i - sub_len]
            localMin = min(localSum, localMin)
        return  sum(cardPoints) - localMin

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        points = cardPoints[-k:] + cardPoints[:k]
        curr = 0
        max_ = 0
        for ind, score in enumerate(points):
            if ind >= k:
                curr -= points[ind-k]
            curr += score
            max_ = max(max_, curr)
        return max_

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        total = sum(cardPoints)
        
        nk = len(cardPoints) - k
        
        if nk == 0:
            return total
        
        current = sum(cardPoints[0:nk])
        max_score = current
        
        for i in range(1, k + 1):
            current = current - cardPoints[i - 1] + cardPoints[nk + i - 1]
            
            max_score = min(max_score, current)
            
        return total - max_score

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        
        total = [0 for _ in range(len(cardPoints))]
        total[0] = cardPoints[0]
        
        for i in range(1, len(cardPoints)):
            total[i] = total[i-1] + cardPoints[i]
            
        max_sum = 0
        for i in range(k+1):
            left = total[k-i-1] if k-i > 0 else 0
            right = total[-1] - total[len(cardPoints)-i-1]
            if left + right > max_sum:
                max_sum = left + right
        
        return max_sum

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        N = len(cardPoints)
        res = float('inf')
        run = 0
        for i, p in enumerate(cardPoints):
            if i >= N-k: run -= cardPoints[i-N+k]
            run += p
            if i >= N-k-1: res = min(res, run)
        return sum(cardPoints) - res