Given an array Arr[], the task is to find the maximum sum of all the elements which are not a part of the longest increasing subsequence.
Example 1:
Input:
n = 6
Arr = {4, 6, 1, 2, 4, 6}
Output: 10
Explaination: Elements are 4 and 6.
Example 2:
Input:
n = 5
Arr = {5, 4, 3, 2, 1}
Output: 14
Explaination: Elements are 5,4,3 and 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxSumLis() which takes the array Arr[] and its size n as input parameters and returns maximum sum of elements not part of LIS.
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ N ≤ 1000
1 ≤ Arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def maxSumLis(self, Arr, n):
        # code here

Solutions:
from bisect import bisect_left

class Solution:

	def maxSumLis(self, Arr, n):
		lis = []
		sum = 0
		lis_sum = [0] * (n + 1)
		lis_sum[0] = 0
		for i in range(n):
			sum += Arr[i]
			index = bisect_left(lis, Arr[i])
			if index == len(lis):
				lis.append(Arr[i])
			else:
				lis[index] = Arr[i]
			lis_sum[index + 1] = lis_sum[index] + Arr[i]
		return sum - lis_sum[len(lis)]


import sys

class Solution:

	def maxSumLis(self, arr, n):
		li = [1] * n
		sumli = arr[:]
		for i in range(1, n):
			for j in range(0, i):
				if arr[i] > arr[j] and li[i] < li[j] + 1:
					li[i] = li[j] + 1
					sumli[i] = max(arr[i] + sumli[j], sumli[i])
				elif arr[i] > arr[j] and li[i] == li[j] + 1:
					sumli[i] = arr[i] + sumli[j]
		maxi = max(li)
		lis = [sumli[x] for x in range(len(li)) if li[x] == maxi]
		mini = min(lis)
		return sum(arr) - mini


class Solution:

	def maxSumLis(self, arr, n):
		totalSum = 0
		for i in range(n):
			totalSum += arr[i]
		dp = [[0] * n for i in range(2)]
		for i in range(n):
			dp[0][i] = 1
			dp[1][i] = arr[i]
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j]:
					if dp[0][i] < dp[0][j] + 1:
						dp[0][i] = dp[0][j] + 1
						dp[1][i] = dp[1][j] + arr[i]
					elif dp[0][i] == dp[0][j] + 1:
						dp[1][i] = min(dp[1][i], dp[1][j] + arr[i])
		maxm = 0
		subtractSum = 0
		for i in range(n):
			if dp[0][i] > maxm:
				maxm = dp[0][i]
				subtractSum = dp[1][i]
			elif dp[0][i] == maxm:
				subtractSum = min(subtractSum, dp[1][i])
		return totalSum - subtractSum


class Solution:

	def maxSumLis(self, Arr, n):
		subseq = [(Arr[0], Arr[0])]
		for item in Arr[1:]:
			if item > subseq[-1][0]:
				subseq.append((item, item + subseq[-1][1]))
			elif item <= subseq[0][0]:
				subseq[0] = (item, item)
			else:
				for i in range(len(subseq) - 1):
					if subseq[i][0] < item <= subseq[i + 1][0]:
						subseq[i + 1] = (item, item + subseq[i][1])
						break
		return sum(Arr) - subseq[-1][1]


from bisect import *

class Solution:

	def maxSumLis(self, Arr, n):
		temp = []
		sum = 0
		S = [0] * (n + 1)
		for i in range(n):
			sum += Arr[i]
			pos = bisect_left(temp, Arr[i])
			if pos == len(temp):
				temp.append(Arr[i])
			else:
				temp[pos] = Arr[i]
			S[pos + 1] = S[pos] + Arr[i]
		return sum - S[len(temp)]


class Solution:

	def maxSumLis(self, Arr, n):
		minSumLongestSubseq = [0] * n
		dp = [1] * n
		totalSum = sum(Arr)
		for i in range(n - 1, -1, -1):
			minSumLongestSubseq[i] = Arr[i]
			for j in range(i + 1, n):
				if Arr[j] > Arr[i]:
					if 1 + dp[j] > dp[i]:
						dp[i] = 1 + dp[j]
						minSumLongestSubseq[i] = Arr[i] + minSumLongestSubseq[j]
					elif 1 + dp[j] == dp[i] and Arr[i] + minSumLongestSubseq[j] < minSumLongestSubseq[i]:
						minSumLongestSubseq[i] = Arr[i] + minSumLongestSubseq[j]
		maxLen = max(dp)
		res = 0
		for (i, e) in enumerate(dp):
			if e == maxLen:
				res = max(res, totalSum - minSumLongestSubseq[i])
		return res


class Solution:

	def maxSumLis(self, arr, n):
		total_sum = sum(arr)
		dp = [[1, num] for num in arr]
		res = min(dp)
		for i in range(n):
			for j in range(i):
				if arr[j] < arr[i]:
					temp = [dp[j][0] + 1, dp[j][1] + arr[i]]
					if temp[0] > dp[i][0]:
						dp[i] = temp
					elif temp[0] == dp[i][0]:
						dp[i][1] = min(temp[1], dp[i][1])
			if res[0] < dp[i][0]:
				res = dp[i]
			elif res[0] == dp[i][0]:
				res = min(res, dp[i])
		return total_sum - res[1]


class Solution:

	def maxSumLis(self, A, N):
		dp = [[-1, -1] for _ in range(N)]
		dp[N - 1] = [1, A[N - 1]]
		for i in reversed(range(N - 1)):
			dp[i] = v = [1, A[i]]
			for j in range(i + 1, N):
				if A[i] < A[j]:
					(L, minv) = (dp[j][0] + 1, dp[j][1] + A[i])
					if L > v[0] or (L == v[0] and minv < v[1]):
						v[:] = (L, minv)
		ans = max(dp, key=lambda x: (x[0], -x[1]))
		return sum(A) - ans[1]


class Solution:

	def maxSumLis(self, A, N):
		dp = [[-1, -1] for _ in range(N)]
		dp[N - 1] = [1, A[N - 1]]
		for i in reversed(range(N - 1)):
			dp[i] = v = [1, A[i]]
			for j in range(i + 1, N):
				if A[i] < A[j]:
					(L, minv) = (dp[j][0] + 1, dp[j][1] + A[i])
					if L > v[0] or (L == v[0] and minv < v[1]):
						v[:] = (L, minv)
		ans = max(dp, key=lambda x: (x[0], -x[1]))
		return sum(A) - ans[1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		Arr = input().split()
		for itr in range(n):
			Arr[itr] = int(Arr[itr])
		ob = Solution()
		print(ob.maxSumLis(Arr, n))


class Solution:

	def maxSumLis(self, Arr, n):
		total = sum(Arr)
		dp = [[0] * n for ele in range(2)]
		for i in range(n):
			dp[0][i] = 1
			dp[1][i] = Arr[i]
		for i in range(1, n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					if dp[0][i] < dp[0][j] + 1:
						dp[0][i] = dp[0][j] + 1
						dp[1][i] = dp[1][j] + Arr[i]
					elif dp[0][i] == dp[0][j] + 1:
						dp[1][i] = min(dp[1][i], dp[1][j] + Arr[i])
		ans = 0
		length = 0
		for i in range(n):
			if dp[0][i] > length:
				length = dp[0][i]
				ans = dp[1][i]
			elif dp[0][i] == length:
				ans = min(ans, dp[1][i])
		return total - ans


class Solution:

	def maxSumLis(self, arr, n):
		if n == 1:
			return 0
		s = 0
		ans = float('inf')
		maxLen = 0
		dp = []
		for i in range(n):
			s += arr[i]
			dp.append([1, arr[i]])
		for i in range(1, n):
			for j in range(0, i):
				if arr[i] > arr[j] and dp[i][0] < dp[j][0] + 1 or (dp[i][0] == dp[j][0] + 1 and dp[i][1] > dp[j][1] + arr[i]):
					dp[i] = [dp[j][0] + 1, dp[j][1] + arr[i]]
			if maxLen < dp[i][0] or (maxLen == dp[i][0] and ans > dp[i][1]):
				maxLen = dp[i][0]
				ans = dp[i][1]
		return s - ans


import bisect

class Solution:

	def maxSumLis(self, arr, n):
		dp = [[-1, -1] for _ in range(n + 1)]
		(dp[0][0], dp[0][1]) = (0, 0)
		(dp[1][0], dp[1][1]) = (1, arr[0])
		for i in range(1, n + 1):
			(dp[i][0], dp[i][1]) = (1, arr[i - 1])
			for j in range(1, i + 1):
				if arr[j - 1] < arr[i - 1] and dp[i][0] < dp[j][0] + 1:
					(dp[i][0], dp[i][1]) = (dp[j][0] + 1, dp[j][1] + arr[i - 1])
				elif arr[j - 1] < arr[i - 1] and dp[i][0] == dp[j][0] + 1:
					dp[i][1] = min(dp[i][1], dp[j][1] + arr[i - 1])
		mx = 0
		sm = float('inf')
		for (a, b) in dp[1:]:
			if mx == a:
				sm = min(sm, b)
			elif mx < a:
				sm = b
				mx = a
		return sum(arr) - sm


class Solution:

	def maxSumLis(self, Arr, n):
		dp = [1 for _ in range(n)]
		sum_a = [0 for i in range(n)]
		sum_all = 0
		for i in Arr:
			sum_all = sum_all + i
		for i in range(n):
			sum_a[i] = Arr[i]
		for i in range(1, n):
			for j in range(0, i):
				if Arr[i] > Arr[j]:
					if dp[i] < 1 + dp[j]:
						dp[i] = 1 + dp[j]
						sum_a[i] = sum_a[j] + Arr[i]
					elif dp[i] == 1 + dp[j]:
						sum_a[i] = min(sum_a[i], sum_a[j] + Arr[i])
		maxi = -10
		sum_max = -10
		for i in range(n):
			temp = maxi
			maxi = max(maxi, dp[i])
			if temp == dp[i]:
				sum_max = min(sum_max, sum_a[i])
			else:
				sum_max = max(sum_max, sum_a[i])
		return sum_all - sum_max


class Solution:

	def maxSumLis(self, arr, n):
		al = sum(arr)
		tab1 = [1] * n
		tab2 = [1] * n
		tab2[:] = arr[:]
		for i in range(n):
			for j in range(i):
				if arr[i] > arr[j]:
					if tab1[i] < tab1[j] + 1:
						tab1[i] = tab1[j] + 1
						tab2[i] = tab2[j] + arr[i]
					elif tab1[i] == tab1[j] + 1:
						tab2[i] = min(tab2[i], tab2[j] + arr[i])
		mx = max(tab1)
		minn = al
		for i in range(n):
			if tab1[i] == mx:
				minn = min(minn, tab2[i])
		return al - minn


class Solution:

	def maxSumLis(self, arr, n):
		dp = [[0] * n for i in range(2)]
		total = sum(arr)
		for i in range(n):
			dp[0][i] = 1
			dp[1][i] = arr[i]
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j]:
					if dp[0][i] < dp[0][j] + 1:
						dp[0][i] = dp[0][j] + 1
						dp[1][i] = dp[1][j] + arr[i]
					elif dp[0][i] == dp[0][j] + 1:
						dp[1][i] = min(dp[1][j] + arr[i], dp[1][i])
		maxi = 0
		maxsubtract = 0
		for i in range(n):
			if dp[0][i] > maxi:
				maxi = dp[0][i]
				maxsubtract = dp[1][i]
			elif dp[0][i] == maxi:
				maxsubtract = min(maxsubtract, dp[1][i])
		return total - maxsubtract


class Solution:

	def maxSumLis(self, Arr, n):
		dp = [1 for i in range(n)]
		dp_of_arr = [[] for i in range(n)]
		dp_of_arr[0].append(0)
		all_ans = []
		for i in range(1, n):
			flag = False
			for j in range(i):
				if Arr[j] < Arr[i]:
					if dp[j] + 1 >= dp[i]:
						dp[i] = dp[j] + 1
						final = j
					flag = True
			if flag:
				for ele in dp_of_arr[final]:
					dp_of_arr[i].append(ele)
			dp_of_arr[i].append(i)
		m = max(dp)
		ans = []
		for i in dp_of_arr:
			if len(i) == m:
				ans.append(i)
		for s in ans:
			st = set(s)
			final_ans = []
			for i in range(n):
				if i not in st:
					final_ans.append(Arr[i])
				all_ans.append(sum(final_ans))
		return max(all_ans)