Skip to content

Instantly share code, notes, and snippets.

@nstawski
Created April 20, 2019 18:58
Show Gist options
  • Save nstawski/fda2f060d966b6562c1517c9fba4acd8 to your computer and use it in GitHub Desktop.
Save nstawski/fda2f060d966b6562c1517c9fba4acd8 to your computer and use it in GitHub Desktop.
Longest increasing subsequence, with basic tests
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
if (!nums || !nums.length) { return 0 }
var increasingSubsequences = [];
var maxSubsequence = {
length: 0,
index: 0
};
for (var i = 0; i < nums.length; i++) {
let element = nums[i];
for (var l = 0; l < increasingSubsequences.length; l++) {
var subsequence = increasingSubsequences[l];
if (element > subsequence[subsequence.length - 1]) {
subsequence.push(element);
if (subsequence.length > maxSubsequence.length) {
maxSubsequence.index = l;
maxSubsequence.length = subsequence.length;
}
}
}
increasingSubsequences.push([element]);
}
return maxSubsequence.length;
};
var testCases = [
{
input: [10,9,2,5,3,7,101,18],
output: 4
},
{
input: [1,2,3,5,3,7,8],
output: 6
},
{
input: [3,2,1,0],
output: 0
},
{
input: [3,2,0,1],
output: 2
},
{
input: [],
output: 0
}
]
testCases.map(function(test) {
var result = lengthOfLIS(test.input);
console.log(`Test result: ${result}, expected: ${test.output}`)
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment