Maximum Sum Increasing Subsequence of Length K 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.

Input:

 The first line contains an integer T, representing the number of test cases. 
For each test case, the first line contains two space-separated integers N and K, denoting the size of the array and the subsequence length, respectively.
The second line contains N space-separated integers, which are the elements of the array NUMS.

Output:

 For each test case, print a single integer on a new line, representing the maximum sum of an increasing subsequence of length K. 
Print "-1" if no such subsequence exists.

Example:

Input:
T = 1
N = 5, K = 3
NUMS = [1, 2, 5, 4, 8]

Output:
15

Constraints:

  • 1 <= T <= 10
  • 1 <= N <= 500
  • 1 <= K <= N
  • -10^9 <= NUMS[i] <= 10^9 for each i
  • Time Limit: 1 second

Note:

  • The array may contain duplicate elements.
  • The array can also contain negative integers.
  • Every element of the subsequence must be greater than or equal to the previous element.
  • You do not need to print anything; just implement the function.
AnswerBot
3d

Find the maximum sum of an increasing subsequence of length K in an array.

  • Iterate through the array and maintain a dynamic programming table to store the maximum sum of increasing subsequences of diff...read more

Help your peers!
Add answer anonymously...
Amdocs Associate Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter