Maximum Sum Subsequenc
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

Question

Maximum Sum Subsequenc

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

Accepted Answer

This was a preety good DP-problem . I struggled a bit initially on finding the DP transition but on carefully observing the constraints of the problem , I figured that a O(N^2*K) DP solution will also pass the Test Cases .

Steps :
1) Initiliase a DP array dp[n][k+1] . Store -INF in all cells initally.
2) Let dp[i][j] store the answer for an array of length i and a subsequence of length j
3) Now, for every i , dp[i][1]=arr[i]
4) For each i , find dp[i][j] for every j from 2 to k
5) For every i>=1 , traverse from i-1 to 0 and check if arr[i] > arr[t] where t = [0,i-1] , if we have arr[i]>arr[t] then dp[i][j] = max(dp[i][j] , arr[i]+dp[t][j-1])
6) Final answer = max(dp[i][k]) where i=[0,n-1]

Accepted Answer

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:

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

Space Complexity: OtherExplanation:

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

Time Complexity: OtherExplanation:

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

Accepted Answer

Dynamic Programming

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’ to -1.
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]’).
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]’).
Finally, return ‘MAXIMUMSUM’.

Space Complexity: OtherExplanation:

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

The space complexity is O(K*N) because we need extra space for the lookup table. Since there are N indices and for each index, we need O{K) extra space as subsequences of K different sizes can end at this index.

Time Complexity: OtherExplanation:

O(K * N^2), where N is the number of elements in the array and K is the length of the subsequence.

The time complexity is O(K * N^2) because we are considering every index. We are looking at all the previous elements for each index, and if the previous element is smaller than the current element, we are updating all the values from size=2 to size = K. So, the overall time complexity becomes O(K * N^2).

Python (3.5)

'''
    Time Complexity: O(K * N^2)
    Space Complexity: O(N * K)

    Where 'N' is the number of elements in the array, 'K' is the size of the subsequence.
'''


def maximumSum(nums, k):

    '''
        The value of MAXSUMS[i][j] represents maximum sum for any subsequence 
        of length j and ending at index i.
    '''
    numsLen = len(nums)
    maxSum = []

    # Initialize all the values of the 'MAXSUM' table with -1.
    for i in range(numsLen):
        temp = []
        for j in range(k + 1):
            temp.append(-1)
        maxSum.append(temp)

    '''
        For each index, the maximum sum of a subsequence having a length of 1 is 
        the value of the element at that index.
    '''
    for idx in range(numsLen):
        maxSum[idx][1] = nums[idx]

    '''
        Here 'ENDIDX' represents the ending index of the subsequence, and
        size represents the size of the subsequence. 
    '''
    for endIdx in range(1, numsLen):
        for prev in range(endIdx):
            if nums[endIdx] >= nums[prev]:
                for size in range(2, k + 1):
                    if maxSum[prev][size - 1] != -1:
                        maxSum[endIdx][size] = max(maxSum[endIdx][size], maxSum[prev][size - 1] + nums[endIdx])


    maximumSum = -1
    for endIdx in range(numsLen):
        maximumSum = max(maximumSum, maxSum[endIdx][k])

    return maximumSum

C++ (g++ 5.4)

/*
    Time Complexity: O(K * N^2)
    Space Complexity: O(N * K)

	Where 'N' is the number of elements in the array, 'K' is the size of the subsequence.
*/

long long maximumSum(vector& nums, int k) {

	/*
		The value of MAXSUMS[i][j] represents maximum sum for any subsequence 
		of length j and ending at index i.
	*/
	int numsLen = nums.size();

	long long maxSum[numsLen][k + 1];

	// Initialize all the values of the 'MAXSUM' table with -1.
	for (int i = 0; i < numsLen; i++) {
		for (int j = 0; j < k + 1; j++) {
			maxSum[i][j] = -1;
		}
	}

	/*
		For each index, the maximum sum of a subsequence having a length of 1 is 
		the value of the element at that index.
	*/
	for (int idx = 0; idx < numsLen; idx++) {
		maxSum[idx][1] = nums[idx];
	}

	/*
		Here 'ENDIDX' represents the ending index of the subsequence, and
		size represents the size of the subsequence. 
	*/
	for (int endIdx = 1; endIdx < numsLen; endIdx++) {
		for (int prev = 0; prev < endIdx; prev++) {

			if (nums[endIdx] >= nums[prev]) {
				for (int size = 2; size <= k; size++) {
					if (maxSum[prev][size - 1] != -1) {
						maxSum[endIdx][size] = max(maxSum[endIdx][size], 
							maxSum[prev][size - 1] + nums[endIdx]);
					}
				}
			}
			
		}
	}

	long long maximumSum = -1;

	for (int endIdx = 0; endIdx < numsLen; endIdx++) {
		maximumSum = max(maximumSum, maxSum[endIdx][k]);
	}

	return maximumSum;

}

Java (SE 1.8)

/*
    Time Complexity: O(K * N^2)
    Space Complexity: O(N * K)

	Where 'N' is the number of elements in the array, 'K' is the size of the subsequence.
*/

import java.util.ArrayList;

public class Solution {
    public static long maximumSum(ArrayList nums, int k) {
        /*
            The value of MAXSUMS[i][j] represents maximum sum for any subsequence 
            of length j and ending at index i.
        */
        int numsLen = nums.size();

        long[][] maxSum = new long[numsLen][k + 1];

        // Initialize all the values of the 'MAXSUM' table with -1.
        for (int i = 0; i < numsLen; i++) {
            for (int j = 0; j < k + 1; j++) {
                maxSum[i][j] = -1;
            }
        }

        /*
            For each index, the maximum sum of a subsequence having a length of 1 is 
            the value of the element at that index.
        */
        for (int idx = 0; idx < numsLen; idx++) {
            maxSum[idx][1] = nums.get(idx);
        }

        /*
            Here 'ENDIDX' represents the ending index of the subsequence, and
            size represents the size of the subsequence. 
        */
        for (int endIdx = 1; endIdx < numsLen; endIdx++) {
            for (int prev = 0; prev < endIdx; prev++) {

                if (nums.get(endIdx) >= nums.get(prev)) {
                    for (int size = 2; size <= k; size++) {
                        if (maxSum[prev][size - 1] != -1) {
                            maxSum[endIdx][size] = Math.max(maxSum[endIdx][size], 
                                maxSum[prev][size - 1] + nums.get(endIdx));
                        }
                    }
                }

            }
        }

        long maximumSum = -1;

        for (int endIdx = 0; endIdx < numsLen; endIdx++) {
            maximumSum = Math.max(maximumSum, maxSum[endIdx][k]);
        }

        return maximumSum;
    }
}

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:

Input Format:

Output Format:

Note:

Constraints:

Top Amdocs Associate Software Engineer interview questions & answers

Popular interview questions of Associate Software Engineer

Top HR questions asked in Amdocs Associate Software Engineer