Longest Increasing Subsequence

Description

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solution(javascript)

// const lengthOfLIS = (nums) => {
//   if (nums.length === 0) {
//     return 0
//   }
//   const temp = new Array(nums.length).fill(1)
//   for (let i = 0; i < nums.length; i++) {
//     for (let j = i + 1; j < nums.length; j++) {
//       // 前面有几个比它小的，他是当前最大的
//       // 如果是递减呢？
//       if ((nums[i] < nums[j]) && (temp[j] < temp[i] + 1)) {
//         temp[j] = temp[i] + 1
//       }
//     }
//   }
//   return Math.max(...temp)
// }

// // DFS / Top-down
// const lengthOfLIS = (nums = []) => {
//   const memo = []
//   const aux = (index) => {
//     if (memo[index] !== undefined) {
//       return memo[index]
//     }
//     let length = 1
//     for (let i = index + 1; i < nums.length; i++) {
//       if (nums[i] > nums[index]) {
//         length = Math.max(
//           length,
//           aux(i) + 1,
//         )
//       }
//     }
//     memo[index] = length
//     return length
//   }
//   let max = 0
//   for (let i = 0; i < nums.length; i++) {
//     max = Math.max(max, aux(i))
//   }
//   return max
// }

// Bottom-up
const lengthOfLIS = (nums = []) => {
  if (nums.length <= 1) {
    return nums.length
  }
  const memo = nums.map(() => 1)
  let max = 1
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] > nums[i]) {
        memo[j] = Math.max(
          memo[j],
          memo[i] + 1,
        )
        max = Math.max(max, memo[j])
      }
    }
  }

  return max
}