https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/

longest-increasing-subsequence.js

// https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
// https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

/**
 * Optimal Substructure:
 * Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending
 *  at index i such that arr[i] is the last element of the LIS.
 * Then, L(i) can be recursively written as:
 * L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
 * L(i) = 1, if no such j exists.
 * To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
 * Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.
 */
function L(arr, max, len) {
  let maxEndingHere = 1;
  // Scan all the numbers
  let idx;
  for (idx = 0; idx < len; idx++) {
    // L(idx) is recursive
    const res = L(arr, max, idx);
    // res is the LIS of L(idx).
    // arr[j] < arr[i]
    if (arr[idx-1] < arr[len-1] && res+1 > maxEndingHere) {
      maxEndingHere = res + 1;
    }
  }
  max = Math.max(max, maxEndingHere);
  return maxEndingHere;
}
function getLIS_inefficient(arr) {
  let length = arr.length;
  let idx;
  let targetIdx;
  const L = new Array(length).fill(1);
  for (idx = 1; idx < length; idx++) {
    let maxNumSoFar = 1;
    for (targetIdx = 0; targetIdx < idx; targetIdx++) {
      if (arr[targetIdx] < arr[idx]) {
        if (maxNumSoFar < arr[targetIdx]) {
          maxNumSoFar = arr[targetIdx];
          L[idx]++;
        }
      }
    }
  }
  return Math.max(...L);
}
function getLIS(arr) {
  return L(arr, 1, arr.length);
}
const arr = [10,22,9,33,21,50,41,60,80];
console.log(getLIS(arr), getLIS(arr) === 6);
console.log(getLIS_inefficient(arr) === 6);