Given an array sequence [A1 , A2 ...An], the task is to find the maximum possible sum of increasing subsequence S of length K such that Si1<=Si2<=Si3.........<=Sin.
 
Example 1:
Input:
N = 8 K = 3
A[] = {8 5 9 10 5 6 19 8}
Output: 38
Explanation:
Possible increasing subsequence of
length 3 with maximum possible
sum is 9 10 19.
Example 2:
Input:
N = 2,K = 2
A[] = {10 5}
Output: -1
Explanation:
Can't make any increasing subsequence 
of length 2.
Your Task:
You don't need to read or print anything. Your task is to complete the function max_sum() which takes sequence A as the first parameter and K as the second parameter and returns the maximum possible sum of K-length increasing subsequnece. If not possible return -1.
Expected Time Complexity: O(max(Ai) * n * log(max(Ai)))
Expected Space Complexity: O(max(Ai))
Contraints:
1 <= n <= 100
1 <= A_{i} <= 100000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def max_sum(self, a, k):

		# Code here



Solutions:
class Solution:

	def max_sum(self, a, k):
		n = len(a)
		dp = [[-1 for i in range(k)] for j in range(n)]
		for i in range(n):
			dp[i][0] = a[i]
			for j in range(1, k):
				for l in range(i):
					if a[l] <= a[i] and dp[l][j - 1] != -1:
						dp[i][j] = max(dp[i][j], dp[l][j - 1] + a[i])
		m = -1
		for i in range(n):
			m = max(m, dp[i][k - 1])
		return m


class Solution:

	def max_sum(self, a, k):
		n = len(a)
		dp = [[-1 for j in range(k + 1)] for i in range(n + 1)]
		for i in range(n):
			dp[i][1] = a[i]
		for p in range(2, k + 1):
			for i in range(1, n):
				for j in range(i):
					if a[i] >= a[j] and dp[j][p - 1] >= 0:
						dp[i][p] = max(dp[i][p], a[i] + dp[j][p - 1])
		mx = -1
		for i in range(n):
			mx = max(mx, dp[i][k])
		return mx


import sys

class Solution:

	def max_sum(self, arr, k):
		dp = [-1] * n
		for i in range(0, n):
			dp[i] = [-1] * (k + 1)
			dp[i][1] = arr[i]
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] <= arr[i]:
					for l in range(1, k):
						if dp[j][l] != -1:
							dp[i][l + 1] = max(dp[i][l + 1], arr[i] + dp[j][l])
		maxans = -2
		for i in range(0, n):
			if dp[i][k] > maxans:
				maxans = dp[i][k]
		return maxans


class Solution:

	def max_sum(self, l, k):
		n = len(l)

		def ss(t):
			if t == 1:
				return l[:]
			x = ss(t - 1)
			v = [0 for _ in range(n)]
			for i in range(n):
				for j in range(i + 1, n):
					if l[i] <= l[j] and x[j] != -float('inf'):
						if v[i] == 0:
							x[i] = l[i] + x[j]
							v[i] = 1
						else:
							x[i] = max(x[i], l[i] + x[j])
			for i in range(n):
				if v[i] == 0:
					x[i] = -float('inf')
			return x[:]
		tt = ss(k)
		ans = max(tt)
		return max(ans, -1)


class Solution:

	def fu(self, s, a, m, maxi, dp, d):
		if m < 0:
			return 0
		if tuple(s) in d:
			return d[tuple(s)]
		ans = -1
		for i in range(m, -1, -1):
			if s == [] or a[i] <= s[-1]:
				if len(s) == k:
					ans = max(maxi, ans)
					dp[i] = ans
					d[tuple(s)] = 1
					continue
				s.append(a[i])
				maxi = sum(s)
			else:
				x = self.fu(s[:len(s) - 1], a, i, maxi - s[-1], dp, d)
				q = s.copy()
				y = self.fu(s, a, i - 1, maxi, dp, d)
				s = q.copy()
				maxi = max(x, y, maxi)
			if len(s) == k:
				ans = max(ans, maxi)
				dp[i] = max(dp[i], ans)
				d[tuple(s)] = 1
		if dp[m] == -1:
			dp[m] = 0
			d[tuple(s)] = 0
		return dp[m]
		pass

	def max_sum(self, a, k):
		if k == 1:
			return max(a)
		dp = [[-1] * n for i in range(k + 1)]
		for i in range(n):
			dp[1][i] = a[i]
		for i in range(2, k + 1):
			for j in range(1, n):
				for x in range(j):
					if a[j] >= a[x] and dp[i - 1][x] >= 0:
						dp[i][j] = max(dp[i][j], dp[i - 1][x] + a[j])
		maxi = -1
		for i in range(n):
			maxi = max(maxi, dp[k][i])
		return maxi


class Solution:

	def max_sum(self, a, k):
		dp = []
		n = len(a)
		for i in range(n):
			l = []
			for j in range(k + 1):
				l.append(-1)
			dp.append(l)
		for i in range(n):
			dp[i][1] = a[i]
		for i in range(2, k + 1):
			for j in range(1, n):
				for k1 in range(j):
					if a[j] >= a[k1] and dp[k1][i - 1] >= 0:
						dp[j][i] = max(dp[j][i], dp[k1][i - 1] + a[j])
		maxi = -1
		for i in range(n):
			if dp[i][k] > maxi:
				maxi = dp[i][k]
		return maxi


class Solution:

	def max_sum(self, a, k):
		dp = [[-1 for x in range(k + 1)] for y in range(len(a))]
		for i in range(len(dp)):
			dp[i][1] = a[i]
		n = len(a)
		for i in range(1, n):
			for j in range(i):
				if a[i] >= a[j]:
					for l in range(1, k):
						if dp[j][l] != -1:
							dp[i][l + 1] = max(dp[i][l + 1], dp[j][l] + a[i])
		ans = -1
		for i in range(n):
			if ans < dp[i][k]:
				ans = dp[i][k]
		return ans


import functools

class Solution:

	def max_sum(self, a, k):
		n = len(a)
		a.append(10 ** 10)

		@functools.lru_cache(None)
		def f(i, k):
			if i == n:
				return 0 if k == 0 else -1
			res = -1
			for j in range(i + 1, n + 1):
				if a[j] >= a[i] and f(j, k - 1) != -1:
					res = max(res, a[i] + f(j, k - 1))
			return res
		return max((f(i, k) for i in range(n)))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		a = list(map(int, input().split()))
		ob = Solution()
		ans = ob.max_sum(a, k)
		print(ans)


class Solution:

	def getFirstSmaller(self, a, n, firstSmaller):
		st = []
		size = 0
		for i in range(n):
			while size > 0 and a[i] < a[st[-1]]:
				del st[-1]
				size -= 1
			if size > 0:
				firstSmaller.append(st[-1])
			else:
				firstSmaller.append(-1)
			st.append(i)
			size += 1
		print(firstSmaller)

	def max_sum(self, a, k):
		n = len(a)
		dp = []
		dp.append([0] * (n + 1))
		for i in range(k):
			dp.append([-1] * (n + 1))
			dp[i + 1][0] = -1
		for i in range(1, k + 1):
			for j in range(1, n + 1):
				if i == 1:
					dp[i][j] = a[j - 1]
					continue
				for l in range(j - 1):
					if a[l] <= a[j - 1] and dp[i - 1][l + 1] != -1:
						dp[i][j] = max(dp[i][j], a[j - 1] + dp[i - 1][l + 1])
		return max(dp[k])


import sys

class Solution:

	def subMaxSum(self, sa, k, si, mk):
		if k < 0:
			return 0
		if mk[si][k] == -1:
			mk[si][k] = 0
			n = len(sa)
			if k == 1:
				mk[si][k] = sa[si][0]
			else:
				found = False
				for i in range(si + 1, n):
					if sa[i][1] > sa[si][1]:
						continue
					sum = self.subMaxSum(sa, k - 1, i, mk)
					if sum > 0:
						mk[si][k] = max(mk[si][k], sa[si][0] + sum)
						found = True
				if not found:
					mk[si][k] = -2
		return mk[si][k]

	def max_sum(self, a, k):
		n = len(a)
		mk = [[-1 for i in range(k + 1)] for j in range(n + 1)]
		sa = []
		for i in range(n):
			sa.append((a[i], i))
		sa.sort(reverse=True)
		maxSum = -1
		for i in range(n):
			sum = self.subMaxSum(sa, k, i, mk)
			if sum > maxSum:
				maxSum = sum
		return maxSum


def solve(dp, pos, k, arr, n):
	if k < 0:
		return 0
	if dp[pos][k] != -1:
		return dp[pos][k]
	dp[pos][k] = 0
	if k == 1:
		dp[pos][k] = arr[pos][0]
		return dp[pos][k]
	b = 0
	for i in range(pos + 1, n):
		if arr[i][1] < arr[pos][1]:
			x = solve(dp, i, k - 1, arr, n)
			if x > 0:
				dp[pos][k] = max(dp[pos][k], arr[pos][0] + x)
				b = 1
	if b == 0:
		dp[pos][k] = -1 * float('inf')
	return dp[pos][k]

class Solution:

	def max_sum(self, a, k):
		n = len(a)
		dp = [[-1 for i in range(k + 1)] for j in range(n + 1)]
		arr = []
		for i in range(n):
			arr.append([a[i], i])
		arr.sort(reverse=True)
		mx = 0
		for i in range(n):
			x = solve(dp, i, k, arr, n)
			mx = max(mx, x)
		if mx == 0:
			return -1
		return mx


class Solution:

	def max_sum(self, a, k):
		n = len(a)
		best = a.copy()
		for t in range(1, k):
			temp = [-float('inf')] * n
			for i in range(n):
				for j in range(i):
					if a[j] <= a[i] and best[j] + a[i] > temp[i]:
						temp[i] = best[j] + a[i]
			best = temp
		res = max(best)
		return res if res > 0 else -1