Jump to content

Longest increasing subsequence: Difference between revisions

Longest increasing subsequence (view source)

Revision as of 07:14, 3 September 2019

162 bytes removed ,  4 years ago
→‎{{header|JavaScript}}
(→‎{{header|REXX}}: added the REXX computer programming language for this task.)
Line 1,047:
 
=={{header|JavaScript}}==
<lang javascript>function getLis(input) {▼
{{libheader|Lo-Dash underscore library}}
var len =if (input.length; === 0) {▼
return output[];▼
}
 
var lisLenPerIndex = [];
▲<lang javascript>
let max = { index: 0, length: 1 };
 
for (var i = 0; i <len input.length; i++) {▼
var _ = require('underscore');
lisLenPerIndex[i] = 1;
function findIndex(input){
for (var j = i - 1; j >= 0; j--) {▼
▲ var len = input.length;
if (input[i] > input[j] && maxSeqEndingHerelisLenPerIndex[j] >= maxSeqEndingHerelisLenPerIndex[i]) {▼
var maxSeqEndingHere = _.range(len).map(function(){return 1;});
var length = lisLenPerIndex[i] = lisLenPerIndex[j] + 1;
▲ for(var i=0; i<len; i++)
if (length > max.length) {
▲ for(var j=i-1;j>=0;j--)
max = { index: i, length };
▲ if(input[i] > input[j] && maxSeqEndingHere[j] >= maxSeqEndingHere[i])
}
maxSeqEndingHere[i] = maxSeqEndingHere[j]+1;
}
return maxSeqEndingHere;
}
}
}
 
var lis = [input[max.index]];
function findSequence(input, result){
for (var i = maxIndex max.index; i >= 0 && max.length !== 0; i--) {▼
var maxValue = Math.max.apply(null, result);
if (input[maxIndexmax.index] > input[i] && resultlisLenPerIndex[i] === maxValuemax.length - 1) {▼
var maxIndex = result.indexOf(Math.max.apply(Math, result));
output lis.pushunshift(input[i]);▼
var output = [];
max.length--;
output.push(input[maxIndex]);
}
▲ for(var i = maxIndex ; i >= 0; i--){
}
if(maxValue==0)break;
 
▲ if(input[maxIndex] > input[i] && result[i] == maxValue-1){
return lis;
▲ output.push(input[i]);
maxValue--;
}
}
output.reverse();
▲ return output;
}
 
var x = 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]));
▲var x = [0, 7, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
var y = [3, 2, 6, 4, 5, 1];
 
var result = findIndex(x);
var final = findSequence(x, result);
console.log(final);
 
var result1 = findIndex(y);
var final1 = findSequence(y, result1);
console.log(final1);
</lang>
 
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/234582"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information