Maximum Sum Subsequence

Hard
0/120
Average time to solve is 45m
profile
Contributed by
19 upvotes
Asked in companies
WalmartAmazonOla

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5 3
1 3 -2 4 5
Sample Output 1:
12
Explanation Of Sample Input 1:
In the first test case, the subsequence having 3(index 1), 4(index 3), and 5(index 4) have the sum of 12, which is the maximum amongst all increasing subsequences having a total of 3 elements. Note that there can be more than one increasing subsequence with the required length, but we have to choose the one which has the maximum sum. In this example, some other such subsequences will be :
1 3 4    sum = 8
1 3 5    sum = 9
1 4 5    sum = 10
3 4 5    sum = 12
-2 4 5  sum = 7
Thus, maximum value of the subsequence is 12.
Sample Input 2:
1
4 3
5 7 4 3
Sample Output 2:
-1
Explanation Of Sample Input 2:
In the first test case, there are a total of 4 subsequences having 3 elements. But none of these subsequences is increasing, so we output “-1”.
Hint

Find all subsequences of length K using recursion.

Approaches (2)
Naive Approach using Recursion

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:

 

  1. Initialize a variable, ‘MAXIMUMSUM’ = -1, to store the maximum sum.
  2. Create a temporary vector, 'SUBSEQUENCE', to store all the subsequences one by one.
  3. 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.
  4. Finally, return the value of ‘MAXIMUMSUM’.

 

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

 

  1. 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.
  2. Call the recursive function for findSubsequences(NUMS, K, CURRINDEX + 1, MAXIMUMSUM, SUBSEQUENCE).
  3. Push the value of the ‘NUMS[CURRINDEX]’ at the end of the ‘SUBSEQUENCE’ vector.
  4. Call the recursive function again for findSubsequences(NUMS, K, CURRINDEX + 1, MAXIMUMSUM, SUBSEQUENCE).
Time Complexity

O(K * nCk), where ‘N’ is the number of elements in the array, and ‘K’ is the length of the subsequence.

 

There are a total of nCk subsequences of size K, and then for every subsequence, we need linear time to check if it’s increasing or not and to find its sum. So, the overall time complexity will be O(K * nCk).

Space Complexity

O(K * nCk), where ‘N’ is the number of elements in the array, and ‘K’ is the length of the subsequence.

 

There can be at most nCk subsequences of size K, and then for every subsequence, we need extra linear space to store that subsequence. So, the overall time complexity will be O(K * nCk).

Code Solution
(100% EXP penalty)
Maximum Sum Subsequence
Full screen
Console