Longest increasing subsequence: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,047: / Line 1,047: @@
 =={{header|JavaScript}}==
+<lang javascript>function getLis(input) {
-{{libheader|Lo-Dash underscore library}}
+  if (input.length === 0) {
+    return [];
+  }
+  var lisLenPerIndex = [];
-<lang javascript>
+  let max = { index: 0, length: 1 };
+  for (var i = 0; i < 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] && lisLenPerIndex[j] >= lisLenPerIndex[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 = max.index; i >= 0 && max.length !== 0; i--) {
-	var maxValue = Math.max.apply(null, result);
+    if (input[max.index] > input[i] && lisLenPerIndex[i] === max.length - 1) {
-	var maxIndex = result.indexOf(Math.max.apply(Math, result));
+      lis.unshift(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;
 }
+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>