Longest increasing subsequence: Difference between revisions
Content added Content deleted
(Added JavaScript Patience sorting method) |
|||
Line 1,402: | Line 1,402: | ||
return lis; |
return lis; |
||
} |
|||
console.log(getLongestIncreasingSubsequence([0, 7, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15])); |
|||
console.log(getLongestIncreasingSubsequence([3, 2, 6, 4, 5, 1])); |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
[ 0, 2, 6, 9, 11, 15 ] |
|||
[ 2, 4, 5 ] |
|||
</pre> |
|||
===Patience sorting=== |
|||
<lang JavaScript>function getLIS(input) { |
|||
if (input.length === 0) { |
|||
return 0; |
|||
} |
|||
const piles = [input[0]]; |
|||
for (let i = 1; i < input.length; i++) { |
|||
const leftPileIdx = binarySearch(piles, input[i]); |
|||
if (leftPileIdx !== -1) { |
|||
piles[leftPileIdx] = input[i]; |
|||
} else { |
|||
piles.push(input[i]); |
|||
} |
|||
} |
|||
return piles.length; |
|||
} |
|||
function binarySearch(arr, target) { |
|||
let lo = 0; |
|||
let hi = arr.length - 1; |
|||
while (lo <= hi) { |
|||
const mid = lo + Math.floor((hi - lo) / 2); |
|||
if (arr[mid] >= target) { |
|||
hi = mid - 1; |
|||
} else { |
|||
lo = mid + 1; |
|||
} |
|||
} |
|||
return lo < arr.length ? lo : -1; |
|||
} |
} |
||