You are given an array A of length N .You have to find the maximum sum subsequence of a given sequence such that all elements of the subsequence are sorted in strictly increasing order. If there are more than one such subsequences,then print the sequence which ends closest to the starting index of the string.
Example 1:
Input: N = 7
A = {1, 101, 2, 3, 100, 4, 5}
Output: {1, 2, 3, 100}
Explaination: This subsequence has the
highest sum of 106.
Example 2:
Input: N = 5
A = {4, 2, 5, 3, 4}
Output: {4, 5}
Explaination: Here the subsequence {2, 3,
4} also  provides the sum 9. But that
ends at index 4. So, answer here is the
sequence {4, 5} which ends at 2nd index.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxSumSequence() which takes the array and N and returns the sequence.
Expected Time Complexity: O(N*N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 1000
1 ≤ A[ i ] ≤ 10000

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    def maxSumSequence(self, N, A):
        # code here

Solutions:
class Solution:

	def maxSumSequence(self, N, A):
		lis = [[i] for i in A]
		for i in range(1, len(A)):
			for j in range(0, i):
				if A[i] > A[j] and sum(lis[i]) < sum(lis[j]) + A[i]:
					lis[i] = lis[j].copy()
					lis[i].append(A[i])
		ans = [0]
		for i in lis:
			if sum(i) > sum(ans):
				ans = i.copy()
		return ans


class Solution:

	def maxSumSequence(self, N, A):
		dp = [[[], 0] for i in range(N)]
		dp[0][1] = A[0]
		dp[0][0].append(0)
		m1 = A[0]
		m2 = [0]
		for i in range(1, N):
			res1 = 0
			res2 = []
			for j in range(i):
				if A[j] < A[i]:
					if res1 < dp[j][1]:
						res1 = dp[j][1]
						res2 = dp[j][0].copy()
			res2.append(i)
			res1 += A[i]
			dp[i][0] = res2.copy()
			dp[i][1] = res1
			if m1 < res1:
				m1 = res1
				m2 = res2
			elif m1 == res1:
				if res2[0] < m2[0]:
					m2 = res2
		for i in range(len(m2)):
			m2[i] = A[m2[i]]
		return m2


class Solution:

	def maxSumSequence(self, n, arr):
		from collections import defaultdict
		d = defaultdict(list)
		dp = [-1] * n
		for i in range(n):
			ans = arr[i]
			for j in range(i):
				if arr[j] < arr[i] and ans < arr[i] + dp[j]:
					ans = dp[j] + arr[i]
					d[i] = [] + d[j]
			d[i].append(arr[i])
			dp[i] = ans
		ans = 0
		maxi = -float('inf')
		for i in range(n):
			if dp[i] > maxi:
				maxi = dp[i]
				ans = d[i]
		return ans


class Solution:

	def maxSumSequence(self, N, A):
		d = [A[i] for i in range(N)]
		heap = [i for i in range(N)]
		summ = [i for i in A]
		maxi = 0
		for i in range(N):
			for j in range(i):
				if A[j] < A[i] and d[j] + A[i] > d[i]:
					d[i] = d[j] + A[i]
					heap[i] = j
			maxi = max(maxi, d[i])
		w = {}
		for i in range(N):
			if d[i] != maxi:
				continue
			c = i
			ans = []
			while True:
				ans += [A[c]]
				if c == heap[c]:
					break
				c = heap[c]
			w[c] = ans
		return sorted(w[min(w)])


class Solution:

	def maxSumSequence(self, n, a):
		dp = [0] * n
		dp[0] = a[0]
		d = {}
		d[dp[0]] = [0]
		for i in range(1, n):
			s = 0
			for j in range(i - 1, -1, -1):
				if a[j] < a[i]:
					s = max(s, dp[j])
			dp[i] = s + a[i]
			if dp[i] not in d:
				d[dp[i]] = [i]
			else:
				d[dp[i]].append(i)
		r = max(dp)
		for k in d[r]:
			i = k
			break
		re = []
		while r >= 0:
			re.append(a[i])
			v = r
			r -= a[i]
			if r not in d:
				break
			for j in d[r]:
				if j < i and a[j] < a[i]:
					i = j
					break
			if v == r:
				break
		l = [int(i) for i in reversed(re)]
		return l


class Solution:

	def maxSumSequence(self, N, A):
		dp = [[0, -1] for i in range(N)]
		dp[0][0] = A[0]
		ma = A[0]
		idx1 = 0
		for i in range(1, N):
			m = 0
			idx = -1
			for j in range(i):
				if A[i] > A[j]:
					if dp[j][0] > m:
						m = dp[j][0]
						idx = j
			dp[i][0] = m + A[i]
			dp[i][1] = idx
			if dp[i][0] > ma:
				ma = dp[i][0]
				idx1 = i
		ans = []
		while idx1 != -1:
			ans.append(A[idx1])
			idx1 = dp[idx1][1]
		return ans[::-1]


class Solution:

	def maxSumSequence(self, n, arr):
		l = [(ele, index) for (index, ele) in enumerate(arr)]
		for i in range(1, n):
			for j in range(i):
				if arr[j] < arr[i] and l[j][0] + arr[i] > l[i][0]:
					l[i] = (l[j][0] + arr[i], j)
		(max_, max_index) = l[0]
		current = 0
		for i in range(1, n):
			if l[i][0] > max_:
				(max_, max_index) = l[i]
				current = i
		ans = [arr[current]]
		while max_index != current:
			ans.append(arr[max_index])
			current = max_index
			max_index = l[max_index][1]
		return ans[-1::-1]


class Solution:

	def maxSumSequence(self, n, a):
		arr1 = [0] * n
		arr2 = [-1] * n
		arr1[0] = a[0]
		for i in range(1, n):
			arr1[i] = a[i]
			for j in range(i):
				if a[j] < a[i]:
					if arr1[i] < arr1[j] + a[i]:
						arr1[i] = arr1[j] + a[i]
						arr2[i] = j
		mini = -1
		indi = 0
		for i in range(n):
			if arr1[i] > mini:
				mini = arr1[i]
				indi = i
		ans = []
		ind = indi
		ans.append(a[ind])
		while ind > 0:
			ind = arr2[ind]
			if ind >= 0:
				ans.insert(0, a[ind])
		return ans


class Solution:

	def maxSumSequence(self, N, A):
		s = [i for i in A]
		sequence = [None for i in A]
		m_id = 0
		for i in range(1, len(A)):
			for j in range(i):
				if A[i] > A[j] and s[j] + A[i] > s[i]:
					s[i] = s[j] + A[i]
					sequence[i] = j
			if s[i] > s[m_id]:
				m_id = i
		result = []
		while m_id is not None:
			result.append(A[m_id])
			m_id = sequence[m_id]
		result = list(reversed(result))
		return result


class Solution:

	def maxSumSequence(self, N, A):
		dp = [[] for i in range(N)]
		dp[0].append(A[0])
		for i in range(1, N):
			for j in range(i):
				if A[i] > A[j] and sum(dp[j]) > sum(dp[i]):
					dp[i] = dp[j].copy()
			dp[i].append(A[i])
		maxx = 0
		index = 0
		for i in range(N):
			if sum(dp[i]) > maxx:
				maxx = sum(dp[i])
				index = i
		return dp[index]