logo CodeStepByStep logo

maxSubsequenceK

Language/Type: C++ dynamic programming

Write a function named maxSubsequenceK that finds and returns the maximum possible sum of any increasing subsequence of values of length k in a given vector, using dynamic programming. Your function accepts two parameters: a reference to a vector of integers, and an integer target K. For example, if the vector stores {8, 5, 9, 10, 5, 6, 21, 8} and k is 3, the value returned should be 40 because it is the sum of the 3-element subsequence {9, 10, 21}.

The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach. Do not use recursion. You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm. You may assume that no value in the vector is negative.

Function: Write a C++ function as described, not a complete program.

You must log in before you can solve this problem.

Log In

Need help?

Stuck on an exercise? Contact your TA or instructor.

If something seems wrong with our site, please

Is there a problem? Contact us.