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: MEDIUM
Tags: Data structures

Amortized analysis

Range queries
Skill types: Amortized analysis

Data structures

Range queries

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
		for x in range(k):
			all += cardPoints[x + n]
			window -= cardPoints[x]
			window += cardPoints[x + n]
			if window < min:
				min = window
		return 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:
		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:
		(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:
		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:
		n = len(cardPoints)
		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


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
		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:
		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


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
		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:
		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)
		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:
		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:
		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:
		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
		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])
			elif i == k:
				max_score = max(max_score, front[k - 1])
			else:
				max_score = max(max_score, front[i - 1] + back[k - i - 1])
		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:
		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, 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:
		total = sum(cardPoints[:k])
		if k == len(cardPoints):
			return total
		max_sum = total
		print(max_sum)
		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) - 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):
			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]
		if k == n:
			return total
		w = n - k
		result = 0
		for i in range(w - 1, n):
			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
		for i in range(k):
			currSum = currSum - cardPoints[size - k + i] + cardPoints[i]
			ans = max(ans, currSum)
		return ans


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
		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_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 = []
		temp_left = 0
		for (i, v) in enumerate(cardPoints):
			pre_sum.append(temp_left)
			temp_left += v
		pre_sum.append(temp_left)
		post_sum = []
		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()
		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
		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:
		ans = win = 0
		for i in range(-k, k):
			win += cardPoints[i]
			if i >= 0:
				win -= cardPoints[i - k]
			ans = max(win, ans)
		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:
		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])
		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