Given an array and a number k, find the largest sum of the subarray containing at least k numbers. It may be assumed that the size of array is at-least k.
 
Example 1:
Input : 
n = 4
arr[] = {-4, -2, 1, -3}
k = 2
Output : 
-1
Explanation :
The sub array is {-2, 1}
 
Example 2:
Input :
n = 6 
arr[] = {1, 1, 1, 1, 1, 1}
k = 2
Output : 
6
Explanation :
The sub array is {1, 1, 1, 1, 1, 1}
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxSumWithK() which takes the array A[], its size N and an integer K as inputs and returns the value of the largest sum of the subarray containing at least k numbers.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
 
Constraints:
1<=n<=10^{5}
-10^{5}<=a[i]<=10^{5}
1<=k<=n

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Amortized analysis

Starter code: #User function Template for python3



def maxSumWithK( a, n, k):

    

    

    

    

Solutions:
def maxSumWithK(a, n, k):
	res = kandane(a, n)
	(beg, end, aux_sum, sum) = (0, 0, 0, float('-inf'))
	while end < n:
		aux_sum += a[end]
		if end - beg + 1 == k:
			temp = res[beg - 1] if beg - 1 >= 0 else float('-inf')
			ans = max(aux_sum, aux_sum + temp)
			sum = max(sum, ans)
			aux_sum -= a[beg]
			beg += 1
		end += 1
	return sum

def kandane(a, n):
	res = [0] * n
	(aux_sum, sum) = (0, float('-inf'))
	for i in range(n):
		aux_sum += a[i]
		if aux_sum < a[i]:
			aux_sum = a[i]
		res[i] = aux_sum
	return res


def maxSumWithK(a, n, k):
	maxSum = [0] * n
	maxSum[0] = a[0]
	curr_max = a[0]
	for i in range(1, n):
		curr_max = max(a[i], curr_max + a[i])
		maxSum[i] = curr_max
	sum = 0
	for i in range(k):
		sum += a[i]
	result = sum
	for i in range(k, n):
		sum = sum + a[i] - a[i - k]
		result = max(result, sum)
		result = max(result, sum + maxSum[i - k])
	return result


def maxSumWithK(a, n, k):
	res = kandane(a, n)
	(sum, aux_sum) = (float('-inf'), 0)
	for i in range(0, k):
		aux_sum += a[i]
	sum = max(sum, aux_sum)
	for i in range(k, n):
		aux_sum = aux_sum - a[i - k] + a[i]
		ans = max(aux_sum, aux_sum + res[i - k])
		sum = max(sum, ans)
	return sum

def kandane(a, n):
	res = [0] * n
	(aux_sum, sum) = (0, float('-inf'))
	for i in range(n):
		aux_sum += a[i]
		if aux_sum < a[i]:
			aux_sum = a[i]
		res[i] = aux_sum
	return res


def maxSumWithK(a, n, k):
	ans = -float('inf')
	curr = 0
	prev = 0
	for i in range(n):
		if i < k:
			curr += a[i]
			prev += a[i]
		else:
			ans = max(ans, curr, prev)
			prev += a[i] - a[i - k]
			curr += a[i]
			curr = max(curr, prev)
	ans = max(ans, prev, curr)
	return ans


def maxSumWithK(a, n, k):
	sumarr = 0
	for i in range(k):
		sumarr += a[i]
	ans = sumarr
	j = 0
	last = 0
	for i in range(k, n):
		sumarr += a[i]
		ans = max(ans, sumarr)
		last += a[j]
		j += 1
		if last < 0:
			sumarr -= last
			last = 0
			ans = max(ans, sumarr)
	return ans


def maxSumWithK(a, n, k):
	max_sum = float('-inf')
	prefix_sum = [0] * (n + 1)
	min_prefix_sum = [0] * (n + 1)
	prefix_sum[0] = 0
	for i in range(1, n + 1):
		prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]
	min_prefix_sum[0] = prefix_sum[0]
	for i in range(1, n + 1):
		min_prefix_sum[i] = min(min_prefix_sum[i - 1], prefix_sum[i])
	for i in range(k, n + 1):
		max_sum = max(max_sum, prefix_sum[i] - min_prefix_sum[i - k])
	return max_sum


import sys

def maxSumWithK(a, n, k):
	max_sum = -sys.maxsize
	curr_sum = 0
	sum = 0
	for i in range(n):
		if i < k:
			curr_sum += a[i]
			sum += a[i]
		else:
			max_sum = max(curr_sum, sum, max_sum)
			curr_sum += a[i] - a[i - k]
			sum += a[i]
			sum = max(curr_sum, sum)
	max_sum = max(curr_sum, sum, max_sum)
	return max_sum


import sys

def maxSumWithK(a, n, k):
	max_sum = -sys.maxsize
	sum = 0
	for i in range(k):
		sum += a[i]
	last = 0
	j = 0
	max_sum = max(sum, max_sum)
	for i in range(k, n):
		sum += a[i]
		last += a[j]
		j += 1
		max_sum = max(sum, max_sum)
		if last < 0:
			sum = sum - last
			max_sum = max(sum, max_sum)
			last = 0
	return max_sum


import sys

def maxSumWithK(a, n, k):
	max_sum = [0 for i in range(n)]
	max_sum[0] = a[0]
	cur_max = a[0]
	for i in range(1, n):
		cur_max = max(a[i], cur_max + a[i])
		max_sum[i] = cur_max
	sum = 0
	for i in range(k):
		sum += a[i]
	res = sum
	for i in range(k, n):
		sum = sum + a[i] - a[i - k]
		res = max(sum, res)
		res = max(res, sum + max_sum[i - k])
	return res


def maxSumWithK(a, n, k):
	max_sum = [0] * n
	cur_sum = 0
	for i in range(n):
		cur_sum = max(cur_sum + a[i], a[i])
		max_sum[i] = cur_sum
	s = 0
	for i in range(k):
		s += a[i]
	res = s
	for i in range(k, n):
		s += a[i] - a[i - k]
		res = max(res, s)
		res = max(res, s + max_sum[i - k])
	return res


def maxSumWithK(a, n, k):
	res = -1000000000.0
	i = 0
	j = 0
	sums = 0
	iwin = 0
	iwinmin = 0
	while i < n:
		sums += a[i]
		if i - j + 1 == k:
			res = max(res, sums)
		if i - j + 1 > k:
			iwin += a[j]
			j += 1
			iwinmin = min(iwinmin, iwin)
			res = max(res, sums - iwinmin)
		i += 1
	return res


def maxSumWithK(arr, n, k):
	maxi = float('-inf')
	cursum = arr[0]
	bestsubarray = [cursum]
	for i in range(1, n):
		if cursum > 0:
			cursum += arr[i]
		else:
			cursum = arr[i]
		bestsubarray.append(cursum)
	exactk = 0
	for i in range(k):
		exactk += arr[i]
	if exactk > maxi:
		maxi = exactk
	for i in range(k, n):
		exactk += arr[i] - arr[i - k]
		if exactk > maxi:
			maxi = exactk
		morethank = exactk + bestsubarray[i - k]
		if morethank > maxi:
			maxi = morethank
	return maxi


import sys

def maxSumWithK(a, n, k):
	ans = -sys.maxsize - 1
	currsum = ans = sum(a[0:k])
	arr = []
	kadane = 0
	for i in range(n):
		if kadane > -1:
			kadane += a[i]
		else:
			kadane = a[i]
		arr.append(kadane)
	j = k - 1
	i = 0
	while j < n - 1:
		j += 1
		currsum += a[j]
		currsum -= a[i]
		i += 1
		if arr[i - 1] > 0:
			ans = max(ans, currsum + arr[i - 1])
		ans = max(currsum, ans)
	return ans


def maxSumWithK(a, n, k):
	s = 0
	for i in range(k):
		s += a[i]
	ans = s
	p = 0
	ps = 0
	for i in range(k, n):
		ps += a[i - k]
		p = min(p, ps)
		s += a[i]
		if s - p > ans:
			ans = s - p
	return ans


def kadens(nums):
	dp = [0] * len(nums)
	cur_sum = nums[0]
	dp[0] = nums[0]
	for i in range(1, len(nums)):
		cur_sum = max(cur_sum + nums[i], nums[i])
		dp[i] = cur_sum
	return dp

def maxSumWithK(nums, n, k):
	arr = kadens(nums)
	exactK = 0
	ans = float('-inf')
	for i in range(k):
		exactK += nums[i]
	if exactK > ans:
		ans = exactK
	for j in range(k, len(nums)):
		exactK += nums[j] - nums[j - k]
		if exactK > ans:
			ans = exactK
		ans = max(ans, arr[j - k] + exactK)
	return ans


import sys

def maxSumWithK(a, n, k):
	summ = sum(a[0:k])
	ans = summ
	last = 0
	j = 0
	for i in range(k, n):
		summ += a[i]
		last = last + a[j]
		j += 1
		ans = max(ans, summ)
		if last < 0:
			summ = summ - last
			ans = max(ans, summ)
			last = 0
	return ans


def maxSumWithK(a, n, k):
	maxsum = -float('inf')
	sums = 0
	cur = 0
	prev = 0
	for i in range(n):
		if i < k:
			cur += a[i]
			prev += a[i]
		else:
			maxsum = max(maxsum, cur, prev)
			prev += a[i] - a[i - k]
			cur += a[i]
			cur = max(cur, prev)
	maxsum = max(maxsum, prev, cur)
	return maxsum


import sys

def maxSumWithK(l, n, k):
	ans = -float('inf')
	curr = 0
	prev = 0
	for i in range(n):
		if i < k:
			curr += l[i]
			prev += l[i]
		else:
			ans = max(ans, curr, prev)
			prev += l[i] - l[i - k]
			curr += l[i]
			curr = max(curr, prev)
	ans = max(ans, prev, curr)
	return ans


def maxSumWithK(nums, n, k):
	if k > len(nums):
		return -1
	ans = -99999999999
	max_sum = list()
	curr_sum = nums[0]
	max_sum.append(nums[0])
	for i in range(1, len(nums)):
		if curr_sum > 0:
			curr_sum += nums[i]
		else:
			curr_sum = nums[i]
		max_sum.append(curr_sum)
	exactK = 0
	for i in range(k):
		exactK += nums[i]
	if exactK > ans:
		ans = exactK
	for i in range(k, len(nums), 1):
		exactK = exactK + nums[i] - nums[i - k]
		if exactK > ans:
			ans = exactK
		morethanK = max_sum[i - k] + exactK
		if morethanK > ans:
			ans = morethanK
	return ans


def maxSumWithK(nums, n, k):
	summ = 0
	for i in range(k):
		summ += nums[i]
	ans = summ
	prev = 0
	prev_sum = 0
	for i in range(k, n):
		prev_sum += nums[i - k]
		prev = min(prev_sum, prev)
		summ += nums[i]
		if summ - prev > ans:
			ans = summ - prev
	return ans


import sys

def maxSumWithK(a, n, k):
	max_sum = [0] * n
	ans = -sys.maxsize - 1
	curr_sum = a[0]
	max_sum[0] = a[0]
	for i in range(1, n):
		if curr_sum > 0:
			curr_sum += a[i]
		else:
			curr_sum = a[i]
		max_sum[i] = curr_sum
	exactk = 0
	for j in range(k):
		exactk += a[j]
	if ans < exactk:
		ans = exactk
	for m in range(k, n):
		exactk -= a[m - k]
		exactk += a[m]
		if exactk > ans:
			ans = exactk
		morethank = exactk + max_sum[m - k]
		if morethank > ans:
			ans = morethank
	return ans


def maxSumWithK(arr, n, k):
	su = 0
	for i in range(k):
		su += arr[i]
	answer = su
	last = start = 0
	end = k
	while end < n:
		last += arr[start]
		start += 1
		su += arr[end]
		answer = max(answer, su)
		if last < 0:
			su = su - last
			answer = max(answer, su)
			last = 0
		end += 1
	return answer


def maxSumWithK(a, n, k):
	s = sum(a[:k])
	prev = prev_sum = 0
	ans = s
	for i in range(k, n):
		prev_sum += a[i - k]
		prev = min(prev, prev_sum)
		s += a[i]
		ans = max(ans, s - prev)
	return ans


def maxSumWithK(a, n, k):
	maxSumAtIndex = []
	maxSumAtIndex.append(a[0])
	maxSumUpto = a[0]
	for index in range(1, n):
		maxSumUpto = max(a[index], maxSumUpto + a[index])
		maxSumAtIndex.append(maxSumUpto)
	sumK = 0
	for i in range(k):
		sumK += a[i]
	result = sumK
	for i in range(k, n):
		sumK += a[i] - a[i - k]
		curr_sum = max(result, sumK)
		result = max(result, curr_sum)
		result = max(result, sumK + maxSumAtIndex[i - k])
	return result


def maxSumWithK(a, n, k):
	sum1 = sum(a[:k])
	(e, j) = (0, 0)
	ans = -1000000000.0
	ans = max(ans, sum1)
	for i in range(k, n):
		sum1 += a[i]
		e += a[j]
		j += 1
		ans = max(ans, sum1)
		if e < 0:
			sum1 -= e
			ans = max(ans, sum1)
			e = 0
	return ans


import sys

def maxSumWithK(a, n, k):
	sum1 = sum(a[:k])
	(e, j) = (0, 0)
	ans = -sys.maxsize - 1
	ans = max(ans, sum1)
	for i in range(k, n):
		sum1 += a[i]
		e += a[j]
		j += 1
		ans = max(ans, sum1)
		if e < 0:
			sum1 -= e
			ans = max(ans, sum1)
			e = 0
	return ans


def maxSumWithK(a, n, k):
	maxi = sum(a[:k])
	res = maxi
	j = k
	i = 0
	l = 0
	while j < n:
		res = res + a[j]
		l += a[i]
		maxi = res if res > maxi else maxi
		if l < 0:
			res = res - l
			l = 0
			maxi = res if res > maxi else maxi
		i += 1
		j += 1
	return maxi


def maxSumWithK(a, n, k):
	ans = -1000000000.0
	(cur, prev) = (0, 0)
	for i in range(n):
		if i < k:
			cur += a[i]
			prev += a[i]
		else:
			ans = max(ans, cur, prev)
			cur += a[i]
			prev += a[i] - a[i - k]
			cur = max(cur, prev)
	ans = max(ans, cur, prev)
	return ans


def maxSumWithK(a, n, k):
	summa = sum(a[:k])
	max_sum = summa
	extra = 0
	for i in range(n - k):
		summa += a[k + i] - a[i]
		extra += a[i]
		if extra < 0:
			extra = 0
		if summa + extra > max_sum:
			max_sum = summa + extra
	return max_sum


def maxSumWithK(A, n, k):
	pref = [0] * n
	pref[0] = A[0]
	max_here = A[0]
	for i in range(1, n):
		max_here = max(A[i], max_here + A[i])
		pref[i] = max_here
	summ = 0
	for i in range(k):
		summ += A[i]
	ans = summ
	for i in range(k, n):
		summ += A[i] - A[i - k]
		ans = max(ans, summ)
		ans = max(ans, summ + pref[i - k])
	return ans


def maxSumWithK(a, n, k):
	maxi = []
	sum = 0
	for num in a:
		sum += num
		maxi.append(sum)
		if sum < 0:
			sum = 0
	sm = 0
	for i in range(k):
		sm += a[i]
	maximum = -float('inf')
	result = sm
	for i in range(k, n):
		sm += a[i] - a[i - k]
		result = max(sm, result)
		result = max(result, sm + maxi[i - k])
	return result


def maxSumWithK(a, n, k):
	pref = [0] * n
	pref[0] = a[0]
	for i in range(1, n):
		pref[i] = max(a[i], a[i] + pref[i - 1])
	curr_sum = sum(a[:k])
	max_sum = curr_sum
	for i in range(k, n):
		curr_sum = curr_sum + a[i] - a[i - k]
		max_sum = max(max_sum, curr_sum, curr_sum + pref[i - k])
	return max_sum


def maxSumWithK(a, n, k):
	pre = [a[0]] * n
	for i in range(1, n):
		pre[i] = pre[i - 1] + a[i]
	mn = [a[0]] * n
	for i in range(1, n):
		mn[i] = min(mn[i - 1], pre[i])
	mx = [pre[-1]] * n
	for i in range(n - 2, -1, -1):
		mx[i] = max(mx[i + 1], pre[i])
	ans = mx[k - 1]
	for i in range(k, n):
		ans = max(ans, mx[i] - mn[i - k])
	return ans


def maxSumWithK(arr, n, k):
	csum = arr[0]
	maxSum = [0] * n
	maxSum[0] = csum
	for i in range(1, n):
		if csum > 0:
			csum += arr[i]
		else:
			csum = arr[i]
		maxSum[i] = csum
	exactK = sum(arr[:k])
	ans = exactK
	for i in range(k, n):
		exactK += arr[i] - arr[i - k]
		ans = max(ans, exactK)
		biggerThanK = exactK + maxSum[i - k]
		ans = max(ans, biggerThanK)
	return ans


def maxSumWithK(a, n, k):
	csum = a[0]
	F = [0] * n
	F[0] = a[0]
	for i in range(1, n):
		csum = max(csum + a[i], a[i])
		F[i] = csum
	exactk = 0
	ans = -float('inf')
	exactk = sum(a[0:k])
	if ans < exactk:
		ans = sum(a[0:k])
	atleastk = 0
	for i in range(k, n):
		exactk += a[i] - a[i - k]
		ans = max(ans, exactk)
		atleastk = exactk + F[i - k]
		ans = max(atleastk, ans)
	return ans


import sys

def maxSumWithK(nums, n, k):
	maxi = 0
	store = []
	for i in range(n):
		if nums[i] + maxi > nums[i]:
			maxi += nums[i]
		else:
			maxi = nums[i]
		store.append(maxi)
	exactwin = 0
	for i in range(k):
		exactwin += nums[i]
	j = 0
	ans = -sys.maxsize - 1
	if exactwin > ans:
		ans = exactwin
	for i in range(k, n):
		exactwin += nums[i] - nums[i - k]
		if exactwin > ans:
			ans = exactwin
		if exactwin + store[i - k] > ans:
			ans = exactwin + store[i - k]
	return ans


def maxSumWithK(a, n, k):
	prevsum = [0] * len(a)
	prevsum[0] = a[0]
	currsum = 0
	for i in range(1, len(a)):
		if prevsum[i - 1] < 0:
			prevsum[i] = a[i]
			currsum = 0
		else:
			currsum = prevsum[i - 1] + a[i]
			prevsum[i] = currsum
	(ws, we) = (0, 0)
	exactk = 0
	result = float('-inf')
	for we in range(len(a)):
		if we - ws < k:
			exactk += a[we]
		else:
			result = max(result, exactk)
			exactk += a[we] - a[ws]
			atleastk = exactk + prevsum[ws]
			ws += 1
			result = max(result, atleastk, exactk)
	if we - ws >= len(a) - 1:
		return exactk
	return result


def maxSumWithK(a, n, k):
	l = [0 for i in range(n)]
	l[0] = a[0]
	c_sum = a[0]
	for i in range(1, n):
		c_sum = max(a[i], a[i] + c_sum)
		l[i] = c_sum
	sum1 = 0
	for i in range(0, k):
		sum1 += a[i]
	result = sum1
	for i in range(k, n):
		sum1 = sum1 + a[i] - a[i - k]
		result = max(result, sum1)
		result = max(result, sum1 + l[i - k])
	return result


def maxSumWithK(a, n, k):
	sum = 0
	l1 = []
	exa = 0
	for i in range(k):
		exa += a[i]
	ma = ans = exa
	for i in range(k, n):
		exa += a[i] - a[i - k]
		ans = max(ans + a[i], exa)
		if ma < ans:
			ma = ans
	return ma


def maxSumWithK(a, n, k):
	list1 = []
	sum = a[0]
	list1.append(a[0])
	for i in range(1, n):
		if sum >= 0:
			sum += a[i]
		else:
			sum = a[i]
		list1.append(sum)
	sum = 0
	(ans, atleast) = (float('-inf'), 0)
	for j in range(k):
		sum += a[j]
	ans = max(ans, sum)
	for i in range(k, n, 1):
		sum = sum - a[i - k] + a[i]
		ans = max(ans, sum)
		atleast = sum + list1[i - k]
		ans = max(atleast, ans)
	return ans


def maxSumWithK(a, n, k):
	s = 0
	m = s = a[0]
	l = [a[0]]
	for i in range(1, len(a)):
		if s >= 0:
			s += a[i]
		else:
			s = a[i]
		l.append(s)
	atleast_k = 0
	exactly_k = sum(a[:k])
	ans = exactly_k
	ans = max(ans, exactly_k)
	for i in range(k, n):
		exactly_k += a[i] - a[i - k]
		ans = max(ans, exactly_k)
		atleast_k = exactly_k + l[i - k]
		ans = max(ans, atleast_k)
	return ans


def maxSumWithK(a, n, k):
	f = [0] * n
	f[0] = a[0]
	s = f[0]
	for i in range(n):
		s = f[i - 1]
		if s >= 0:
			f[i] = f[i - 1] + a[i]
		else:
			f[i] = a[i]
	l = 0
	ans = -9999999999999999999
	for i in range(k):
		l += a[i]
	ans = max(ans, l)
	for i in range(k, n):
		l += a[i] - a[i - k]
		ans = max(ans, l)
		c = l + f[i - k]
		ans = max(ans, c)
	return ans


from math import *

def maxSumWithK(a, n, k):
	f = []
	curr = 0
	ans = -inf
	for i in a:
		if curr > 0:
			curr += i
		else:
			curr = i
		f.append(curr)
	ex = 0
	for i in range(k):
		ex += a[i]
	ans = ex
	atlst = 0
	for i in range(k, n):
		ex += a[i] - a[i - k]
		ans = max(ans, ex)
		atlst = ex + f[i - k]
		ans = max(ans, atlst)
	return ans


def maxSumWithK(a, n, k):
	new = []
	new.append(a[0])
	for i in range(1, len(a)):
		if new[i - 1] >= 0:
			new.append(new[i - 1] + a[i])
		else:
			new.append(a[i])
	sum = 0
	for i in range(k):
		sum += a[i]
	ans = -99999999999999999
	ans = max(ans, sum)
	for i in range(k, n):
		sum += a[i] - a[i - k]
		ans = max(ans, sum)
		c = sum + new[i - k]
		ans = max(ans, c)
	return ans


def maxSumWithK(a, n, k):
	f = [0 for i in range(n)]
	s = a[0]
	f[0] = s
	for i in range(1, n):
		if s > 0:
			s += a[i]
		else:
			s = a[i]
		f[i] = s
	ex = 0
	ans = float('-inf')
	for i in range(k):
		ex += a[i]
	ans = max(ans, ex)
	for i in range(k, n):
		ex += a[i] - a[i - k]
		ans = max(ans, ex)
		at = ex + f[i - k]
		ans = max(ans, at)
	return ans


def maxSumWithK(a, n, k):
	f = [0] * n
	f[0] = a[0]
	for i in range(1, n):
		if f[i - 1] > 0:
			f[i] = a[i] + f[i - 1]
		else:
			f[i] = a[i]
	exact_k = 0
	for i in range(k):
		exact_k += a[i]
	ans = exact_k
	for i in range(k, n):
		exact_k += a[i] - a[i - k]
		ans = max(ans, exact_k)
		atleast_k = exact_k + f[i - k]
		ans = max(ans, atleast_k)
	return ans


def maxSumWithK(a, n, k):
	gs = a[0]
	m = float('-inf')
	l = []
	l.append(a[0])
	for i in range(1, len(a)):
		if gs >= 0:
			gs += a[i]
		else:
			gs = a[i]
		l.append(gs)
	j = k
	i = 0
	s = sum(a[:k])
	m = s
	while j != n:
		s += a[j] - a[i]
		m = max(m, s)
		e = s + l[i]
		m = max(m, e)
		j += 1
		i += 1
	return m


def maxSumWithK(arr, n, k):
	forward = [0] * len(arr)
	forward[0] = arr[0]
	for i in range(1, len(arr)):
		if forward[i - 1] + arr[i] >= arr[i]:
			forward[i] = arr[i] + forward[i - 1]
		else:
			forward[i] = arr[i]
	ws = 0
	exactK = 0
	atleastK = 0
	res = float('-inf')
	for i in range(k):
		exactK += arr[i]
	res = max(res, exactK)
	for we in range(k, len(arr)):
		exactK += arr[we] - arr[ws]
		atleastK = forward[ws] + exactK
		res = max(res, exactK, atleastK)
		ws += 1
	return res


def maxSumWithK(arr, n, k):
	forward = [arr[0]]
	for i in range(1, len(arr)):
		forward.append(max(arr[i], arr[i] + forward[i - 1]))
	exactk = sum(arr[:k])
	ans = exactk
	atleast = 0
	for i in range(k, n):
		exactk += arr[i] - arr[i - k]
		ans = max(ans, exactk)
		atleast = exactk + forward[i - k]
		ans = max(ans, atleast)
	return ans


def maxSumWithK(a, n, k):
	count = 0
	dpf = [0] * n
	for i in range(k):
		count += a[i]
	dpf[0] = a[0]
	csum = a[0]
	ans = count
	for i in range(1, n):
		if csum >= 0:
			csum += a[i]
		else:
			csum = a[i]
		dpf[i] = csum
	atleast = 0
	for i in range(k, n):
		count += a[i] - a[i - k]
		ans = max(ans, count)
		atleast = count + dpf[i - k]
		ans = max(ans, atleast)
	return ans


def maxSumWithK(nums, n, k):

	def findMaxSubarray(nums):
		maxSum = nums[0]
		currsum = 0
		res = []
		for i in nums:
			currsum += i
			res.append(currsum)
			if currsum < 0:
				currsum = 0
		return res
	arr1 = findMaxSubarray(nums)
	res = 0
	for i in range(k):
		res += nums[i]
	exactK = res
	for i in range(k, len(arr1)):
		exactK += nums[i] - nums[i - k]
		atleastk = exactK + arr1[i - k]
		res = max(res, exactK, atleastk)
	return res


import math

def maxSumWithK(a, n, k):
	pre = [0] * n
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = a[i] + pre[i - 1]
	for i in range(1, n):
		a[i] = max(a[i], a[i] + a[i - 1])
	ans = -math.inf
	for i in range(k - 1, n):
		if i == k - 1:
			ans = max(ans, pre[i])
		elif i == k:
			x = max(pre[i], pre[i] - pre[i - k])
			ans = max(ans, x)
		else:
			x = max(a[i - k] + pre[i] - pre[i - k], pre[i] - pre[i - k])
			ans = max(x, ans)
	return ans


def maxSumWithK(a, n, k):
	p = [a[0]]
	for i in range(1, n):
		val = a[i]
		p.append(max(p[i - 1] + val, val))
	win_sum = sum(a[:k])
	res = win_sum
	for i in range(k, n):
		prev = i - k
		win_sum -= a[prev]
		win_sum += a[i]
		res = max(res, win_sum, win_sum + p[prev])
	return res