search

trekhleb / javascript-algorithms

📝 Algorithms and data structures implemented in JavaScript with explanations and links to further readings
MIT License
188.58k stars 30.28k forks source link

Return `longestIncreasingSubsequence` from `dpLongestIncreasingSubsequence` #1164

Open shola opened 3 months ago

shola commented 3 months ago

The Longest Increasing Subsequence README.md and dpLongestIncreasingSubsequence.test.js give examples of the longest increasing subsequence that will be generated from various sequences:

In the first 16 terms of the binary Van der Corput sequence

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

a longest increasing subsequence is

0, 2, 6, 9, 11, 15.

However, the implemented algorithm only returns the length of the longest increasing subsequence, not the subsequence itself. This change will create the longestIncreasingSubsequence from the lengthsArray and return that instead of longestIncreasingLength.

The tests have been updated to expect a subsequence instead of length.

shola commented 2 months ago

@trekhleb what do you think of this change?