Maximum Sum Subsequence

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

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:

1. Store the size of the array in a variable, ‘NUMSLEN’.
2. 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.
3. Initialize all the values of ‘MAXSUM’ to -1.
4. 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]’.
5. 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]’).
6. Finally, declare a variable ‘MAXIMUMSUM’ and initialize it to -1.
7. Run a loop from ‘ENDIDX’ = 0 to ‘ENDIDX’ < ‘NUMSLEN’ and,
   • Upadte ‘MAXIMUMSUM’ = max('MAXIMUMSUM', ‘MAXSUM[ENDIDX][K]’).
8. Finally, return ‘MAXIMUMSUM’.