Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a strictly increasing subsequence. 
Example 1:
Input: N = 5, arr[] = {1, 101, 2, 3, 100} 
Output: 106
Explanation:The maximum sum of a
increasing sequence is obtained from
{1, 2, 3, 100}
Example 2:
Input: N = 3, arr[] = {1, 2, 3}
Output: 6
Explanation:The maximum sum of a
increasing sequence is obtained from
{1, 2, 3}
Your Task:  
You don't need to read input or print anything. Complete the function maxSumIS() which takes N and array arr as input parameters and returns the maximum value.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def maxSumIS(self, Arr, n):

		# code here

Solutions:
class Solution:

	def maxSumIS(self, Arr, n):
		T = [Arr[i] for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if Arr[j] < Arr[i]:
					T[i] = max(T[i], T[j] + Arr[i])
		ans = T[0]
		for i in range(1, n):
			if T[i] > ans:
				ans = T[i]
		return ans


class Solution:

	def maxSumIS(self, Arr, n):
		dp = [0] * n
		for i in range(n):
			dp[i] = Arr[i]
		for i in range(1, n):
			for j in range(i):
				if Arr[i] > Arr[j] and dp[i] < dp[j] + Arr[i]:
					dp[i] = dp[j] + Arr[i]
		return max(dp)


class Solution:

	def answer(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])
		return max(sumli)

	def maxSumIS(self, arr, n):
		return ob.answer(arr, n)


class Solution:

	def maxSumIS(self, arr, n):
		LISsum = arr[:]
		for i in range(1, n):
			cur = arr[i]
			for j in range(i):
				prev = arr[j]
				if prev < cur:
					LISsum[i] = max(LISsum[i], LISsum[j] + cur)
		return max(LISsum)


class Solution:

	def maxSumIS(self, arr, n):
		maximum = [num for num in arr]
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] < arr[i] and maximum[i] < maximum[j] + arr[i]:
					maximum[i] = maximum[j] + arr[i]
		return max(maximum)


class Solution:

	def dp_sol(self, Arr, n):
		dp = [0]
		for el in Arr:
			dp.append(el)
		for i in range(1, n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					dp[i + 1] = max(dp[i + 1], Arr[i] + dp[j + 1])
		return max(dp)

	def maxSumIS(self, Arr, n):
		return self.dp_sol(Arr, n)


class Solution:

	def maxSumIS(self, arr, n):
		n = len(arr)
		dp = arr[:]
		for i in range(1, n):
			for j in range(0, i):
				if arr[j] < arr[i]:
					dp[i] = max(dp[i], dp[j] + arr[i])
		return max(dp)


class Solution:

	def maxSumIS(self, Arr, n):
		res = [0] * n
		for a in range(len(Arr)):
			res[a] = Arr[a]
		for i in range(n - 2, -1, -1):
			for j in range(i + 1, n, 1):
				if Arr[i] < Arr[j]:
					res[i] = max(res[i], Arr[i] + res[j])
		return max(res)


class Solution:

	def maxSumIS(self, nums, n):
		n = len(nums)
		dp = [0] * n
		maxi = 0
		for ind in range(n):
			dp[ind] = nums[ind]
			for prev in range(ind):
				if nums[prev] < nums[ind]:
					dp[ind] = max(nums[ind] + dp[prev], dp[ind])
			maxi = max(maxi, dp[ind])
		return maxi


class Solution:

	def maxSumIS(self, arr, n):
		dp = arr.copy()
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and dp[i] < dp[j] + arr[i]:
					dp[i] = dp[j] + arr[i]
		return max(dp)


class Solution:

	def maxSumIS(self, Arr, n):
		a1 = Arr[:]
		b = [i for i in range(n)]
		for i in range(n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					a1[i] = max(a1[i], a1[j] + Arr[i])
		return max(a1)


class Solution:

	def maxSumIS(self, Arr, n):
		a1 = [i for i in Arr]
		b = [[i] for i in range(len(Arr))]
		for i in range(n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					a1[i] = max(a1[i], a1[j] + Arr[i])
					b[i].append(a1[i])
		c = 0
		for i in b:
			if max(a1) in i:
				c = len(i)
		return max(a1)


class Solution:

	def maxSumIS(self, a, n):
		dp = [0 for i in range(n)]
		ans = 0
		for i in range(n):
			dp[i] = a[i]
			for j in range(i):
				if a[i] > a[j] and a[i] + dp[j] >= dp[i]:
					dp[i] = a[i] + dp[j]
		return max(dp)


class Solution:

	def maxSumIS(self, Arr, n):
		stateMap = [0 for i in range(n + 1)]
		for state in range(1, n + 1):
			maxVal = Arr[state - 1]
			for prevState in range(1, state):
				if Arr[prevState - 1] < Arr[state - 1]:
					maxVal = max(maxVal, Arr[state - 1] + stateMap[prevState])
			stateMap[state] = maxVal
		return max(stateMap)


class Solution:

	def maxSumIS(self, Arr, n):
		Arr = [0] + Arr
		n += 1
		dp = [[0] * n for _ in range(n)]
		for i in range(n):
			dp[i][0] = Arr[i]
		for i in range(n - 1, -1, -1):
			for prev in range(i):
				if i == n - 1:
					if Arr[i] > Arr[prev]:
						dp[i][prev] = Arr[i]
					continue
				take = -1
				if Arr[i] > Arr[prev]:
					take = Arr[i] + dp[i + 1][i]
				not_take = dp[i + 1][prev]
				dp[i][prev] = max(take, not_take)
		return dp[1][0]


class Solution:

	def maxSumIS(self, Arr, n):
		mem = [[-1 for i in range(len(Arr) + 1)]]
		return LIS(Arr, mem)

def LIS(nums, dp):
	dp = [0 for i in range(len(nums))]
	for i in range(len(nums)):
		maxx = 0
		for j in range(0, i):
			if nums[j] < nums[i] and dp[j] > maxx:
				maxx = dp[j]
		dp[i] = maxx + nums[i]
	maxx = 0
	for i in range(len(dp)):
		if dp[i] > maxx:
			maxx = dp[i]
	return maxx


import sys

class Solution:

	def maxSumIS(self, arr, n):
		msi = [0] * n
		for i in range(n):
			msi[i] = arr[i]
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j] and msi[i] < msi[j] + arr[i]:
					msi[i] = msi[j] + arr[i]
		return max(msi)


class Solution:

	def maxSumIS(self, a, n):
		s = sum(a)
		dp = [0] * n
		m = a[0]
		dp[0] = a[0]
		for i in range(1, n):
			dp[i] = a[i]
			for j in range(i):
				if a[i] > a[j]:
					dp[i] = max(dp[i], dp[j] + a[i])
			m = max(m, dp[i])
		return m


class Solution:

	def maxSumIS(self, arr, n):
		if not arr:
			return 0
		ans = 0
		dp = [0 for i in range(n + 1)]
		dp[0] = 0
		for i in range(n):
			dp[i] = arr[i]
			for j in range(i):
				if arr[i] > arr[j] and arr[i] + dp[j] >= dp[i]:
					dp[i] = arr[i] + dp[j]
		return max(dp)


class Solution:

	def maxSumIS(self, arr, n):
		dp = [0] * n
		result = 0
		for idx in range(n - 1, -1, -1):
			val = 0
			for idx2 in range(idx + 1, n):
				if arr[idx] < arr[idx2]:
					val = max(val, dp[idx2])
			dp[idx] = val + arr[idx]
			result = max(result, dp[idx])
		return result


class Solution:

	def maxSumIS(self, Arr, n):
		p = []
		for i in range(n):
			j = 0
			max1 = -1
			while j < i:
				if Arr[i] > Arr[j]:
					max1 = max(max1, p[j])
				j += 1
			if max1 == -1:
				p.append(Arr[i])
			else:
				p.append(Arr[i] + max1)
		return max(p)


class Solution:

	def maxSumIS(self, arr, n):
		dp = [i for i in arr]
		for ind in range(n):
			for prev in range(ind):
				if arr[prev] < arr[ind]:
					dp[ind] = max(dp[ind], arr[ind] + dp[prev])
		return max(dp)


class Solution:

	def maxSumIS(self, Arr, n):
		dp = [0 for i in range(n)]
		dp[n - 1] = Arr[n - 1]
		for idx1 in range(n - 2, -1, -1):
			dp[idx1] = Arr[idx1]
			for prev in range(idx1 + 1, n):
				if Arr[prev] > Arr[idx1]:
					dp[idx1] = max(dp[idx1], Arr[idx1] + dp[prev])
		return max(dp)


import math

class Solution:

	def maxSumIS(self, nums, n):
		dp = [0 for _ in range(len(nums))]
		dp[0] = nums[0]
		for i in range(1, len(nums)):
			dp[i] = nums[i]
			for j in range(0, i):
				if nums[j] < nums[i]:
					dp[i] = max(dp[i], dp[j] + nums[i])
		return max(dp)


class Solution:

	def maxSumIS(self, Arr, n):
		mis = [1] * len(Arr)
		for i in range(len(Arr)):
			mis[i] = Arr[i]
		for i in range(len(Arr) - 1, -1, -1):
			for j in range(i + 1, len(Arr)):
				if Arr[i] < Arr[j]:
					mis[i] = max(mis[i], Arr[i] + mis[j])
		return max(mis)


class Solution:

	def maxSumIS(self, arr, n):
		sum1 = [0] * n
		ans = 0
		for i in range(n):
			sum1[i] = arr[i]
			for j in range(i):
				if arr[i] > arr[j] and sum1[j] + arr[i] > sum1[i]:
					sum1[i] = sum1[j] + arr[i]
			ans = max(sum1[i], ans)
		return ans


class Solution:

	def helper(self, A, i, prev):
		key = (i, prev)
		if self.d.get(key) is not None:
			return self.d[key]
		if i == len(A):
			return 0
		if A[i] > prev:
			self.d[key] = max(A[i] + self.helper(A, i + 1, A[i]), self.helper(A, i + 1, prev))
		else:
			self.d[key] = self.helper(A, i + 1, prev)
		return self.d[key]

	def maxSumIS(self, A, n):
		dp = []
		dp = A[:]
		for i in range(n - 1, -1, -1):
			for j in range(n - 1, i, -1):
				if A[i] < A[j]:
					dp[i] = max(dp[j] + A[i], dp[i])
		return max(dp)


class Solution:

	def helper(self, ind, prev, arr, n, dp):
		if ind == n:
			return 0
		if dp[ind][prev + 1] != -1:
			return dp[ind][prev + 1]
		nottake = self.helper(ind + 1, prev, arr, n, dp)
		take = -1000000000.0
		if prev == -1 or arr[ind] > arr[prev]:
			take = arr[ind] + self.helper(ind + 1, ind, arr, n, dp)
		dp[ind][prev + 1] = max(take, nottake)
		return dp[ind][prev + 1]

	def maxSumIS(self, arr, n):
		dp = [arr[i] for i in range(n)]
		maxi = -1000000000.0
		for i in range(n):
			for j in range(i):
				if arr[i] > arr[j]:
					if dp[i] < dp[j] + arr[i]:
						dp[i] = dp[j] + arr[i]
		for i in range(n):
			maxi = max(maxi, dp[i])
		return maxi


class Solution:

	def maxSumIS(self, Arr, n):
		amax = [Arr[i] for i in range(n)]
		aseq = [i for i in range(n)]
		for i in range(1, n):
			for j in range(0, i):
				if Arr[j] < Arr[i]:
					asum = amax[j] + Arr[i]
					if asum > amax[i]:
						amax[i] = asum
						aseq[i] = j
		return max(amax)


class Solution:

	def maxSumIS(self, Arr, n):
		sum = 0
		msis = [0 for x in range(n)]
		for i in range(n):
			msis[i] = Arr[i]
		for i in range(1, n):
			for j in range(i):
				if Arr[i] > Arr[j] and msis[i] < msis[j] + Arr[i]:
					msis[i] = msis[j] + Arr[i]
		for i in range(n):
			if sum < msis[i]:
				sum = msis[i]
		return sum


class Solution:

	def maxSumIS(self, nums, n):
		n = len(nums)
		dp = [0 for i in range(n)]
		dp[0] = nums[0]
		ans = nums[0]
		for i in range(1, n):
			mx = 0
			for j in range(i):
				x = nums[i] - nums[j]
				if x > 0:
					mx = max(mx, dp[j])
			dp[i] = nums[i] + mx
			ans = max(ans, dp[i])
		return ans


class Solution:

	def maxSumIS(self, Arr, n):
		dp = [x for x in Arr]
		ans = Arr[0]
		for i in range(n):
			for j in range(i):
				if Arr[j] < Arr[i]:
					dp[i] = max(dp[j] + Arr[i], dp[i])
			ans = max(ans, dp[i])
		return ans


class Solution:

	def fun(self, idx, arr, n, prev, dp):
		if idx == n:
			return 0
		if dp[idx][prev + 1] != -1:
			return dp[idx][prev + 1]
		np = 0 + self.fun(idx + 1, arr, n, prev, dp)
		p = float('-inf')
		if prev == -1 or arr[prev] < arr[idx]:
			p = arr[idx] + self.fun(idx + 1, arr, n, idx, dp)
		dp[idx][prev + 1] = max(p, np)
		return dp[idx][prev + 1]

	def maxSumIS(self, arr, n):
		dp = [0] * n
		for i in range(n):
			dp[i] = Arr[i]
			for j in range(i):
				if Arr[i] > Arr[j] and dp[i] < dp[j] + Arr[i]:
					dp[i] = dp[j] + Arr[i]
		return max(dp)


class Solution:

	def maxSumIS(self, a, n):
		tab = [[0] * (n + 1) for _ in range(n + 1)]
		for cur in range(n - 1, -1, -1):
			for prev in range(cur - 1, -2, -1):
				take = 0
				if prev == -1 or a[cur] > a[prev]:
					take = a[cur] + tab[cur + 1][cur + 1]
				not_take = tab[cur + 1][prev + 1]
				tab[cur][prev + 1] = max(take, not_take)
		return tab[0][0]

	def memo(self, cur, prev, a, n):
		if cur == n:
			return 0
		if self.dp[cur][prev] is not None:
			return self.dp[cur][prev]
		take = 0
		if prev == -1 or a[cur] > a[prev]:
			take = a[cur] + self.recursive(cur + 1, cur, a, n)
		not_take = self.recursive(cur + 1, prev, a, n)
		self.dp[cur][prev] = max(take, not_take)
		return self.dp[cur][prev]

	def recursive(self, cur, prev, a, n):
		if cur == n:
			return 0
		take = 0
		if prev == -1 or a[cur] > a[prev]:
			take = a[cur] + self.recursive(cur + 1, cur, a, n)
		not_take = self.recursive(cur + 1, prev, a, n)
		return max(take, not_take)


class Solution:

	def maxSumIS(self, a, n):
		lis = [None] * n
		lis[0] = a[0]
		for i in range(1, n):
			lis[i] = a[i]
			for j in range(i):
				if a[j] < a[i]:
					lis[i] = max(lis[i], lis[j] + a[i])
		result = lis[0]
		for i in range(1, len(lis)):
			result = max(result, lis[i])
		return result


class Solution:

	def maxSumIS(self, A, n):

		def manu(A, ind, prev):
			nex = [A[i] for i in range(n)]
			maxi = 0
			for i in range(n):
				for j in range(0, i):
					if A[j] < A[i]:
						nex[i] = max(nex[i], A[i] + nex[j])
				maxi = max(maxi, nex[i])
			return maxi
		return manu(A, 0, -1)


class Solution:

	def maxSumIS(self, Arr, n):
		t = [Arr[i] for i in range(n)]
		gmax = 0
		for i in range(n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					t[i] = max(t[i], t[j] + Arr[i])
			gmax = max(gmax, t[i])
		return gmax


class Solution:

	def bisectleft(self, Arr, l, r, val):
		while l < r:
			mid = (l + r) // 2
			if Arr[mid] > val:
				r = mid
			else:
				l = mid + 1
		return l

	def maxSumIS(self, Arr, n):
		t = [Arr[i] for i in range(n)]
		gmax = 0
		for i in range(n):
			for j in range(i):
				if Arr[i] > Arr[j]:
					t[i] = max(t[i], t[j] + Arr[i])
			gmax = max(gmax, t[i])
		return gmax