from collections import defaultdict
 
dp = defaultdict(lambda: -1)
prefixsum = []
trace = []
 
def getSubArraySum(i, j):
	if i == 0:
		return prefixsum[j]
	return (prefixsum[j] - prefixsum[i - 1])
 
def rec(cur, arr, k):
	if cur >= len(arr):
		return 0
	if dp[cur] != -1:
		return dp[cur]
 
	s1 = -1; s2 = -1
	# If we choose the subarray starting at `cur`
	if cur + k - 1 < len(arr):
		s1 = getSubArraySum(cur, cur + k - 1) + rec(cur + k + 1, arr, k)
	# If we ignore the subarray starting at `cur`
	s2 = rec(cur + 1, arr, k)
 
	dp[cur] = max(s1, s2)
 
	if s1 >= s2:
		trace[cur] = (True, cur + k + 1)
		return s1
	trace[cur] = (False, cur + 1)
	return s2
 
def getTrace(arr, trace, k):
	itr = 0
	subArrays = []
	while itr < len(trace):
		if trace[itr][0]:
			subArrays.append(arr[itr : itr + k])
		itr = trace[itr][1]
	return subArrays
 
def solve(arr, k):
	global dp, trace, prefixsum
 
	dp = defaultdict(lambda: -1)
	trace = [(False, 0)] * len(arr)
	prefixsum = [0] * len(arr)
 
	prefixsum[0] = arr[0]
	for i in range(1, len(arr)):
		prefixsum[i] += prefixsum[i - 1] + arr[i]
 
	print("Array :", arr)
	print("Max sum: ", rec(0, arr, k))
	print("Subarrays: ", getTrace(arr, trace, k))
	print("-- * --")
 
solve([1, 2, 3, 4], 3)
solve([1, 2, 3, 1, 7, 9] , 2)
solve([1, 5, 3, 1, 7, 9] , 1)

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVmYXVsdGRpY3QKCmRwID0gZGVmYXVsdGRpY3QobGFtYmRhOiAtMSkKcHJlZml4c3VtID0gW10KdHJhY2UgPSBbXQoKZGVmIGdldFN1YkFycmF5U3VtKGksIGopOgoJaWYgaSA9PSAwOgoJCXJldHVybiBwcmVmaXhzdW1bal0KCXJldHVybiAocHJlZml4c3VtW2pdIC0gcHJlZml4c3VtW2kgLSAxXSkKCmRlZiByZWMoY3VyLCBhcnIsIGspOgoJaWYgY3VyID49IGxlbihhcnIpOgoJCXJldHVybiAwCglpZiBkcFtjdXJdICE9IC0xOgoJCXJldHVybiBkcFtjdXJdCgkKCXMxID0gLTE7IHMyID0gLTEKCSMgSWYgd2UgY2hvb3NlIHRoZSBzdWJhcnJheSBzdGFydGluZyBhdCBgY3VyYAoJaWYgY3VyICsgayAtIDEgPCBsZW4oYXJyKToKCQlzMSA9IGdldFN1YkFycmF5U3VtKGN1ciwgY3VyICsgayAtIDEpICsgcmVjKGN1ciArIGsgKyAxLCBhcnIsIGspCgkjIElmIHdlIGlnbm9yZSB0aGUgc3ViYXJyYXkgc3RhcnRpbmcgYXQgYGN1cmAKCXMyID0gcmVjKGN1ciArIDEsIGFyciwgaykKCQoJZHBbY3VyXSA9IG1heChzMSwgczIpCgkKCWlmIHMxID49IHMyOgoJCXRyYWNlW2N1cl0gPSAoVHJ1ZSwgY3VyICsgayArIDEpCgkJcmV0dXJuIHMxCgl0cmFjZVtjdXJdID0gKEZhbHNlLCBjdXIgKyAxKQoJcmV0dXJuIHMyCgpkZWYgZ2V0VHJhY2UoYXJyLCB0cmFjZSwgayk6CglpdHIgPSAwCglzdWJBcnJheXMgPSBbXQoJd2hpbGUgaXRyIDwgbGVuKHRyYWNlKToKCQlpZiB0cmFjZVtpdHJdWzBdOgoJCQlzdWJBcnJheXMuYXBwZW5kKGFycltpdHIgOiBpdHIgKyBrXSkKCQlpdHIgPSB0cmFjZVtpdHJdWzFdCglyZXR1cm4gc3ViQXJyYXlzCgpkZWYgc29sdmUoYXJyLCBrKToKCWdsb2JhbCBkcCwgdHJhY2UsIHByZWZpeHN1bQoJCglkcCA9IGRlZmF1bHRkaWN0KGxhbWJkYTogLTEpCgl0cmFjZSA9IFsoRmFsc2UsIDApXSAqIGxlbihhcnIpCglwcmVmaXhzdW0gPSBbMF0gKiBsZW4oYXJyKQoJCglwcmVmaXhzdW1bMF0gPSBhcnJbMF0KCWZvciBpIGluIHJhbmdlKDEsIGxlbihhcnIpKToKCQlwcmVmaXhzdW1baV0gKz0gcHJlZml4c3VtW2kgLSAxXSArIGFycltpXQoJCglwcmludCgiQXJyYXkgOiIsIGFycikKCXByaW50KCJNYXggc3VtOiAiLCByZWMoMCwgYXJyLCBrKSkKCXByaW50KCJTdWJhcnJheXM6ICIsIGdldFRyYWNlKGFyciwgdHJhY2UsIGspKQoJcHJpbnQoIi0tICogLS0iKQoKc29sdmUoWzEsIDIsIDMsIDRdLCAzKQpzb2x2ZShbMSwgMiwgMywgMSwgNywgOV0gLCAyKQpzb2x2ZShbMSwgNSwgMywgMSwgNywgOV0gLCAxKQ==