searching/longest-increasing-subsequence.js

  1. (function (exports) {
  2.   'use strict';
  4.   exports.longestIncreasingSubsequence = (function () {
  6.     /**
  7.     * Find the index of the first largest element in array.
  8.     * Complexity: O(N).
  9.     *
  10.     * @private
  11.     * @param {Array} array The array in which the largest
  12.     *  element should be found.
  13.     * @return {Number} index of the first largest element
  14.     */
  15.     function max(array) {
  16.       if (!array || !array.length) {
  17.         return -1;
  18.       }
  19.       var maxIdx = 0;
  20.       for (var i = 1; i < array.length; i += 1) {
  21.         if (array[maxIdx].distance < array[i].distance) {
  22.           maxIdx = i;
  23.         }
  24.       }
  25.       return maxIdx;
  26.     }
  28.     /**
  29.     * Default comparison method.
  30.     * @private
  31.     */
  32.     function asc(a, b) {
  33.       return a - b;
  34.     }
  36.     /**
  37.     * Creates directed graph from given array.
  38.     * Each element's neighbours are the elements which can be
  39.     * after the element in the resulting sequence.<br><br>
  40.     * Complexity: O(N^2).
  41.     * @private
  42.     * @param  {Array} array The input array.
  43.     * @param  {Function} cmp Comparator.
  44.     * @return {Object} Graph represented with list of neighbours.
  45.     */
  46.     function buildDag(array, cmp) {
  47.       var result = [];
  48.       for (var i = 0; i < array.length; i += 1) {
  49.         result[i] = [];
  50.         for (var j = i + 1; j < array.length; j += 1) {
  51.           if (cmp(array[i], array[j]) < 0) {
  52.             result[i].push(j);
  53.           }
  54.         }
  55.       }
  56.       return result;
  57.     }
  59.     /**
  60.     * Finds the longest increasing sub-sequence for given node.<br><br>
  61.     * Complexity: O(N^N).
  62.     * @private
  63.     * @param {Object} dag  Graph represented with list of neighbours.
  64.     * @param {number} node The current node.
  65.     * @return {object} The longest increasing sub-sequence for given node.
  66.     */
  67.     function find(dag, node) {
  68.       node = node || 0;
  69.       if (find.memo[node]) {
  70.         return find.memo[node];
  71.       }
  72.       var neighbours = dag[node];
  73.       var neighboursDistance = [];
  74.       var maxDist;
  75.       // var maxNode;
  76.       var distance;
  77.       var result;
  79.       if (!neighbours.length) {
  80.         return { distance: 1, neighbour: undefined, node: node };
  81.       }
  83.       for (var i = 0; i < neighbours.length; i += 1) {
  84.         neighboursDistance[i] = find(dag, neighbours[i]);
  85.       }
  87.       maxDist = max(neighboursDistance);
  88.       // maxNode = neighbours[maxDist];
  89.       distance = 1 + neighboursDistance[maxDist].distance;
  90.       find.memo[node] = result = {
  91.         distance: distance,
  92.         neighbour: neighboursDistance[maxDist],
  93.         node: node
  94.       };
  95.       return result;
  96.     }
  98.     /**
  99.     * Algorithm from dynamic programming. It finds the longest
  100.     * sub-sequence of increasing numbers. It is not required
  101.     * the numbers to be neighboring. For example for 1, 5, 2
  102.     * sequence the longest sub-sequence is 1, 2.
  103.     *
  104.     * @example
  105.     * var subsequence = require('path-to-algorithms/src/searching/'+
  106.     * 'longest-increasing-subsequence').longestIncreasingSubsequence;
  107.     * console.log(subsequence([1, 0, 4, 3, 5])); // 1, 4, 5
  108.     *
  109.     * @public
  110.     * @module searching/longest-increasing-subsequence
  111.     * @param {Array} array Input sequence.
  112.     * @param {Function} cmp Comparator.
  113.     * @return {Array} Longest increasing subsequence.
  114.     */
  115.     return function (array, cmp) {
  116.       cmp = cmp || asc;
  117.       var results = [];
  118.       var dag = buildDag(array, cmp);
  119.       var maxPath;
  120.       find.memo = [];
  121.       for (var i = 0; i < array.length; i += 1) {
  122.         results.push(find(dag, i));
  123.       }
  124.       maxPath = results[max(results)];
  125.       results = [];
  126.       while (maxPath) {
  127.         results.push(array[maxPath.node]);
  128.         maxPath = maxPath.neighbour;
  129.       }
  130.       return results;
  131.     };
  132.   })();
  134. })(typeof window === 'undefined' ? module.exports : window);