logo CodeStepByStep logo

longestSortedSubsequence

Language/Type: Java dynamic programming

Write a method named longestSortedSubsequence that accepts an array of integers and returns the length of the longest non-decreasing subsequence of values in the array using dynamic programming. A subsequence contains values in the same order they occurred in the original array, though not necessarily consecutively. For example, if the array stores {10, 22, 9, 33, 21, 50, 41, 60, 80}, the longest sorted subsequence is {10, 22, 33, 50, 60, 80}, so the value returned should be its length, which is 6.

The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach. Do not use recursion. Your solution must use dynamic programming instead.

You are allowed to construct any data structures (array, list, set, map, etc.) necessary to store the data for your dynamic programming algorithm.

Type your Java solution code here:


This is a method exercise. Write a Java method as described. Do not write a complete program or class; just the method(s) above.

You must log in before you can solve this problem.

Log In

Need help?

If you do not understand how to solve an exercise or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect tests, etc.), please

Is there a problem? Contact a site administrator.

©, all rights reserved.