Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning.
Example 1:
Input:
n = 7
k = 3
arr = [1,15,7,9,2,5,10]
Output:
84
Explanation:
arr becomes [15,15,15,9,10,10,10]
Example 2:
Input:
n = 1
k = 1
arr = [1]
Output:
1
Your Task:
You don't have to read input or print anything. Your task is to complete the function Solve() which takes the integer n and array arr and integer k and returns the Largest Sum of the Array after Partitioning.
Expected Time Complexity: O(n^{2})
Expected Space Complexity: O(n)
Constraint:
1 <= n <= 500
0 <= arr[i] <= 10^{9}
1 <= k <= n

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def solve(self, n, k, arr):

        # Code here

Solutions:
class Solution:

	def solve(self, n, k, arr):
		import math
		dp = [0] * (n + 1)
		dp[n] = 0
		i = n - 1
		while i >= 0:
			(ln, maxi) = (0, -math.inf)
			ans = -math.inf
			for j in range(i, min(n, i + k)):
				ln += 1
				maxi = max(maxi, arr[j])
				sm = ln * maxi + dp[j + 1]
				ans = max(sm, ans)
			dp[i] = ans
			i -= 1
		return dp[0]


class Solution:

	def solve(self, n, k, nums):
		dp = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			res = mx = float('-inf')
			for (ln, j) in enumerate(range(i, min(i + k, n)), start=1):
				mx = max(mx, nums[j])
				sm = ln * mx + dp[j + 1]
				res = max(res, sm)
			dp[i] = res
		return dp[0]


class Solution:

	def fun(self, idx, n, k, arr, dp):
		if idx == n:
			return 0
		if dp[idx] != -1:
			return dp[idx]
		length = 0
		(maxi, maxans) = (float('-inf'), float('-inf'))
		for j in range(idx, min(n, idx + k)):
			length += 1
			maxi = max(maxi, arr[j])
			total = length * maxi + self.fun(j + 1, n, k, arr, dp)
			maxans = max(maxans, total)
		dp[idx] = maxans
		return dp[idx]

	def solve(self, n, k, arr):
		dp = [0 for i in range(n + 1)]
		for idx in range(n - 1, -1, -1):
			length = 0
			(maxi, maxans) = (float('-inf'), float('-inf'))
			for j in range(idx, min(n, idx + k)):
				length += 1
				maxi = max(maxi, arr[j])
				total = length * maxi + dp[j + 1]
				maxans = max(maxans, total)
			dp[idx] = maxans
		return dp[0]


class Solution:

	def recur(self, i, k, arr, n, dp):
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		max_ans = float('-inf')
		length = 0
		maxi = float('-inf')
		for j in range(i, min(i + k, n)):
			length += 1
			maxi = max(maxi, arr[j])
			sum = length * maxi + self.recur(j + 1, k, arr, n, dp)
			max_ans = max(max_ans, sum)
		dp[i] = max_ans
		return max_ans

	def solve(self, n, k, arr):
		dp = [float('-inf') for i in range(n)]
		dp.append(0)
		for i in range(n - 1, -1, -1):
			maxi = float('-inf')
			length = 0
			for j in range(i, min(i + k, n)):
				length += 1
				maxi = max(maxi, arr[j])
				sum = length * maxi + dp[j + 1]
				dp[i] = max(dp[i], sum)
		return dp[0]


class Solution:

	def solve(self, n, k, arr):
		dp = [[-1 for i in range(n + 1)] for j in range(n + 1)]

		def recursive(left=0, right=0, cur_max=0):
			nonlocal dp, n, k, arr
			if left >= n:
				return 0
			if right >= n:
				return -float('inf')
			if dp[left][right] != -1:
				return dp[left][right]
			cur_max = max(cur_max, arr[right])
			dp[left][right] = cur_max * (right - left + 1) + recursive(right + 1, right + 1, 0)
			if right - left + 1 < k:
				dp[left][right] = max(dp[left][right], recursive(left, right + 1, cur_max))
			return dp[left][right]
		return recursive()


class Solution:

	def solve(self, n, k, num):

		def memo(idx, k):
			if idx == n:
				return 0
			if dp[idx] != -1:
				return dp[idx]
			lent = 0
			maxi = float('-inf')
			maxans = float('-inf')
			for j in range(idx, min(idx + k, n)):
				lent += 1
				maxi = max(maxi, num[j])
				summ = lent * maxi + memo(j + 1, k)
				maxans = max(maxans, summ)
			dp[idx] = maxans
			return dp[idx]
		dp = [-1] * n
		return memo(0, k)


class Solution:

	def solve(self, n, k, arr):
		n = len(arr)
		dp = {}

		def f(i):
			if i in dp:
				return dp[i]
			if i >= n:
				return 0
			maxi = -9999999999
			length = 0
			max_num = -999999999
			for j in range(i, min(n, i + k)):
				max_num = max(max_num, arr[j])
				length += 1
				cost = max_num * length + f(j + 1)
				maxi = max(maxi, cost)
			dp[i] = maxi
			return maxi
		return f(0)


class Solution:

	def solve(self, n, k, arr):
		dp = [0 for _ in range(n + 1)]
		for ind in range(n - 1, -1, -1):
			maxi = -1000000000.0
			maxSum = -1000000000.0
			length = 0
			for j in range(ind, min(ind + k, n)):
				length += 1
				maxi = max(maxi, arr[j])
				summ = length * maxi + dp[j + 1]
				maxSum = max(maxSum, summ)
			dp[ind] = maxSum
		return dp[0]


class Solution:

	def solve(self, n, k, arr):
		dp = [0] * (n + 1)
		for i in range(n - 1, -1, -1):
			length = 0
			maxi = 0
			res = 0
			for j in range(i, min(i + k, n)):
				length += 1
				maxi = max(maxi, arr[j])
				sum = length * maxi + dp[j + 1]
				res = max(res, sum)
			dp[i] = res
		return dp[0]


from collections import defaultdict

class Solution:

	def solve(self, n, k, arr):
		t = [0 for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			sub_size = 0
			sub_max = float('-inf')
			max_ans = float('-inf')
			for j in range(i, min(n, i + k)):
				sub_size += 1
				sub_max = max(sub_max, arr[j])
				max_ans = max(max_ans, sub_max * sub_size + t[j + 1])
			t[i] = max_ans
		return t[0]


from collections import defaultdict

class Solution:

	def solve(self, n, k, arr):
		n = len(arr)
		dp = [0] * (n + 1)
		for ind in range(n - 1, -1, -1):
			len1 = 0
			max_ans = float('-inf')
			maxi = float('-inf')
			for j in range(ind, min(n, ind + k)):
				len1 += 1
				maxi = max(maxi, arr[j])
				sum1 = len1 * maxi + dp[j + 1]
				max_ans = max(max_ans, sum1)
			dp[ind] = max_ans
		return dp[ind]


import sys

class Solution:

	def partition(self, arr, k, i, n, dp):
		if i == n:
			return 0
		if dp[i] != -1:
			return dp[i]
		(ans, maxEle, l) = (-sys.maxsize, -sys.maxsize, 0)
		for j in range(i, min(i + k, n)):
			maxEle = max(arr[j], maxEle)
			l += 1
			temp = l * maxEle + self.partition(arr, k, j + 1, n, dp)
			ans = max(temp, ans)
		dp[i] = ans
		return ans

	def solve(self, n, k, arr):
		dp = [-1 for i in range(n + 1)]
		return self.partition(arr, k, 0, n, dp)


class Solution:

	def solve(self, n, k, arr):

		def helper(index):
			if index == n:
				return 0
			if dp[index] != -1:
				return dp[index]
			l = 0
			currMax = 0
			currSum = 0
			ans = 0
			for j in range(index, min(n, index + k)):
				l += 1
				currMax = max(currMax, arr[j])
				currSum = l * currMax + helper(j + 1)
				ans = max(ans, currSum)
			dp[index] = ans
			return dp[index]
		dp = [-1 for _ in range(n)]
		return helper(0)


class Solution:

	def solve(self, n, k, arr):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			for j in range(n):
				c = j
			curmax = 0
			best = 0
			j = 1
			while j <= k and i - j >= 0:
				curmax = max(curmax, arr[i - j])
				best = max(best, dp[i - j] + curmax * j)
				j = j + 1
			dp[i] = best
		return dp[n]