Maximum Sum Subsequence

Posted: 10 Mar, 2021
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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 1

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).
Try Problem