# Maximum Sum Subsequence

#### You are given an array “NUMS” consisting of N integers and an integer, K. Your task is to determine the maximum sum of an increasing subsequence of length K.

##### Note:

```
1. The array may contain duplicate elements.
2. The array can also contain negative integers.
3. Every element of the subsequence must be greater than or equal to the previous element.
```

#### The subsequence of an array is a sequence of numbers that can be formed by deleting some or no elements without changing the order of the remaining elements. For example, if the given array “NUMS” = {1, 2, 5, 4, 8}, then {1, 2, 5, 4, 8}, {1, 5, 8}, {2} are some of the valid subsequences whereas the sequence {4, 2} is not a valid subsequence as the order of the elements differ from the original array.

##### Input Format:

```
The first line contains an integer T, which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains two space-separated integers N and K, denoting the number of elements in the array and the length of the subsequence to be considered.
The second line of each test case contains N space-separated integers, representing the elements of the array.
```

##### Output Format:

```
For each test case, print in a new line, an integer denoting the maximum sum of an increasing subsequence of length K.
Print “-1” if no such subsequence exists.
```

##### Note:

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= T <= 10
1 <= N <= 500
1 <= K <= N
-10^9 <= NUMS[i] <= 10^9
Where NUMS[i] represents the i-th element of the array.
Time Limit: 1 sec
```

**Approach: **The approach is to find all subsequences of length ‘K’ using recursion and check whether it is increasing or not. If it is and its sum is more than the maximum sum that we have gotten so far, we update the maximum sum with this subsequence sum.

After we are done with every such subsequence, we return the maximum sum.

This approach might exceed the time limit in most of the test cases.

**Algorithm:**

- Initialize a variable, ‘MAXIMUMSUM’ = -1, to store the maximum sum.
- Create a temporary vector, 'SUBSEQUENCE', to store all the subsequences one by one.
- Create a recursive function,
**solve(CURRINDEX, SUBSEQUENCE, NUMS, K, MAXIMUMSUM)**and call it for 'CURRINDEX' = 0. This function will find all subsequences of size K and update the ‘MAXIMUMSUM’ with the maximum sum among all these subsequences, and if there is no such subsequence, it will remain -1. - Finally, return the value of ‘MAXIMUMSUM’.

**void findSubsequences(NUMS, K, CURRINDEX, MAXIMUMSUM, SUBSEQUENCE) :**

- If ‘CURRINDEX’ equals 'NUMS.size', then,
- If ‘SUBSEQUENCE.size’ is equal to ‘K’, then do :
- Initialize a boolean variable, ‘ISINCREASING’ = true.
- Initialize a variable to store the sum of this subsequence. ‘CURRSUM’ = 'SUBSEQUENCE[0]'.
- Run a loop from ‘i’ = 1 to ‘K’ and do:
- If ‘SUBSEQUENCE[i]’ < ‘SUBSEQUENCE[i - 1]’, make ‘ISINCREASING’ = false and break out of the loop.
- Add ‘SUBSEQUENCE[i]’ to the ‘CURRSUM’.

- If ‘ISINCREASING’ is true, it means that the subsequence is increasing and we update ‘MAXIMUMSUM’ = max(‘MAXIMUMSUM’, ‘CURRSUM’).

- Return from here.

- If ‘SUBSEQUENCE.size’ is equal to ‘K’, then do :
- Call the recursive function for
**findSubsequences(NUMS, K, CURRINDEX + 1, MAXIMUMSUM, SUBSEQUENCE)**. - Push the value of the ‘NUMS[CURRINDEX]’ at the end of the ‘SUBSEQUENCE’ vector.
- Call the recursive function again for
**findSubsequences(NUMS, K, CURRINDEX + 1, MAXIMUMSUM, SUBSEQUENCE)**.

**Approach: **The approach is to use Dynamic Programming. We can create a DP table, and the value present at DP[i][j] will tell us the maximum sum that we can get for any increasing subsequence of length j ending at ith index. Any subsequence of size j - 1 and ending at any index before the current index can be extended to the current index by adding the current element’s value to it, and the size will now become j.

For any index i, DP[i][K] represents the maximum sum that a subsequence of size K ending at this index can have. We can get our answer by finding the maximum value amongst all DP[i][K].

**Algorithm:**

- Store the size of the array in a variable, ‘NUMSLEN’
**.** - Create a 2D array, ‘
**MAXSUM[NUMSLEN][K + 1]’.**The value present at ‘**MAXSUM**[i][j]’ will tell us the maximum sum that we can get for any increasing subsequence of length ‘j’ ending at ith index. - Initialize all the values of ‘MAXSUM’
- For each index, the maximum sum of a subsequence having a length of 1 is the value of the element at that index. So, for all ‘IDX’
**= 0**to**‘IDX’ < ‘NUMSLEN’,**make ‘**MAXSUM[IDX][1]’ = ‘NUMS[IDX]’.** - Run a loop for ‘ENDIDX’
**= 1**to ‘ENDIDX’**< ‘NUMSLEN’**and another loop from ‘PREV’**= 0**to ‘PREV’**< ‘ENDIDX’**and,- If ‘
**NUMS[ENDIDX]’ >= ‘NUMS[PREV]’,**run a loop for ‘**SIZE’ = 2**to**‘SIZE’ < ‘K’**and,- If the value for ‘
**MAXSUM[PREV][SIZE - 1]’**has already been calculated, then update the value of ‘**MAXSUM[ENDIDX][SIZE]’ = max('MAXSUM[ENDIDX][SIZE]', ‘MAXSUM[PREV][SIZE-1] + NUMS[ENDIDX]’).**

- If the value for ‘

- If ‘
- Finally, declare a variable ‘
**MAXIMUMSUM’**and initialize it to -1. - Run a loop from ‘ENDIDX’
**= 0**to**‘ENDIDX’ < ‘NUMSLEN’**and,- Upadte ‘
**MAXIMUMSUM’ = max('MAXIMUMSUM', ‘MAXSUM[ENDIDX][K]’)**.

- Upadte ‘
- Finally, return ‘
**MAXIMUMSUM’.**