Maximum Sum Increasing Subsequence
Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.
Problem description:
Given problem wants you to find the sum of increasing subsequence such that they provide maximum value, this is an application of famous problem of Longest increasing subsequence problem, but here you are required to find the sum not the length so you are required to implement some logic with the help of LIS approach so that it return maximum sum.
Input:
The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N (the size of array). The second line of each test case contains array elements.
Output:
For each test case print the required answer in new line.
Examples:
Input:
T=1
N=5
[9,18,2,4,10]
Output:
27, {9,18} forms the Maximum sum increasing subsequence.
Input:
T=1
N=3
[1,2,3]
Output:
6, {1,2,3} forms the maximum sum increasing subsequence.
This problem is a variation of LIS i.e. longest increasing subsequence problem, we will use recursion approach first to solve the problem:
We have following option with us for each element of the array.
We pick the maximum value obtained from the above two options in our final answer.
Here we are using the solve function to calculate the maximum sum increasing subsequences.
arr[]=is the input array.
The index i is the index, n is the size of the array, prev is the previous sum and sum is the total maximum sum increasing subsequences that we got.
The recursive function will terminate when the index reaches the end of the array if we start to solve from left and if we start from right then the base condition will be if the index is <0.
Time complexity for the above approach in the worst case is exponential
Space complexity for the above approach in the worst case is: O(1)
Dynamic Programming Approach:
In this approach we will use the same logic as Longest increasing subsequence problem, we will create an array sum[] as the same size as of the given array arr[], we will store the value sum[i] as the maximum sum of an increasing subsequence of subarray arr[0...i] that ends with arr[i].
To calculate the sum[i] we will check the maximum sum increasing subsequence of all the smaller values of i that had already been calculated and then we pick the maximum of them.
Time complexity for the above approach in the worst case is : O(n*n)
Space complexity for the above approach in the worst case is: O(n)
C++ Implementation (Recursion approach):
Output:
C++ Implementation (Dynamic Programming):
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer