Longest increasing subsequence (Question Number 300)

The title

Given an array of integers, nums, find the length of the longest strictly increasing subsequence in it. A subsequence is a sequence derived from an array that removes (or does not remove) the elements of the array without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] output: 4 description: the longest increasing subsequence is [2,3,7,101], so the length is 4.Copy the code

Example 2:

Input: NUMs = [0,1,0,3, 3] Output: 4Copy the code

Example 3:

Input: nums = [7,7,7,7,7,7,7,7] output: 1Copy the code

Tip:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

Advanced:

  • Can you design an O(n ^ 2) solution?
  • Can you reduce the time complexity of the algorithm to order nlog n?

link

Leetcode-cn.com/problems/lo…

explain

This problem, this problem can also reluctantly make, but there are still some problems on the idea.

It’s obvious that this is a dynamic programming problem, because it involves repeated states, that is, a state may be used many times, and if you store it, you can avoid calling it the next time, which is the core of dynamic programming: recursion + memorization.

So let’s look at the problem first, longest increasing subsequence, so it’s kind of similar to the way we did it before, we had to know the largest subsequence before we could know the largest subsequence of the next element.

Specifically, it is not the largest subsequence of the previous unit, but the largest subsequence of all previous units that are smaller than the size of the current element. If you find this element and add one, you will find the largest increasing subsequence of the current element.

So first we need to loop through the array, this layer is essential, and then we need to loop through the array again, and this time we need to loop from 0 to I, so the time complexity is O(n ^ 2).

I really can’t think of another O(nlogn) solution, but I can explain it in a better way.

Your own answers (Dynamic Programming)

var lengthOfLIS = function(nums) {
  var obj = new Map()
      arr = []
      max = 0
  for (let i = nums.length - 1; i > -1; i--) {
    var res = 1
    for (let j = 0; j < arr.length; j++) {
      if (nums[i] < arr[j]) {
        res = Math.max(res, 1 + obj.get(arr[j]))
      }
    }
    obj.set(nums[i], res)
    arr.push(nums[i])
    max = Math.max(max, res)
  }
  return max
};
Copy the code

The code looks a little weird, but I wrote it myself.

At that time, my mind did not turn around, thinking of the loop from the back to the front, because it is an increasing subsequence, so the order from large to small, later after looking at other people’s answers, I found that the positive order cycle is the same, there is no difference.

And although DP is used here, the storage of DP is a little too complicated, showing the maximum number of subsequences of each element in an object, followed by an array to store the passed nodes, known as arR.

In this way, we only need to loop arR to get the maximum number of subsequences of the current node, which is the second loop in the explanation.

The index of the array and the elements of the array are completely sufficient. For a better solution, see 👇 :

A better approach (dynamic Programming)

var lengthOfLIS = function(nums) {
  var dp = new Array(nums.length).fill(1)
      max = 1
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
    max = Math.max(max, dp[i])
  }
  return max
};
Copy the code

The dynamic programming is simple. There is only one DP array to store the nodes that have been passed, and then the second level loop is used to determine the length of the DP array to loop through, which is the ARR in your answer.

Then continuously loop the maximum value of the current element in DP, and you can get the maximum number of subsequences of the current element.

A better way (binary search)

The idea of the author think through the head can not come out of this answer, look at the solution, also only a brother with JavaScript gave this answer, the rest are all dynamic programming.

Here’s how it works. The first outermost loop is inevitable, because you have to get each element to compare.

Then you need to maintain a common binary lookup array, which stores the oldest sequence, and update the longest increment subsequence every time you loop through it. Then you can get the longest increment subsequence at the end of the loop. For example, 🌰 :

Suppose the array is: [10,9,2,5,3,7,101,18,20] (20 more than the original question), and the subsequence maintained is LTS.

Let’s start looping through the array:

  • In the first loop, the element is10
    • At this timeltsIf empty, insert directly10.ltsfor[10]
  • In the second loop, the element is9
    • Due to the9than10Small, so I’m just going to10replace9.ltsfor[9]
  • In the third loop, the element is2
    • Due to the2than9Small, then will9replace2.ltsfor[2]
  • In the fourth loop, the element is5
    • Due to the5than2Student: big, so I’m just going to5Add to the end of the array,ltsfor[2, 5]
  • In the fifth loop, the element is3
    • Due to the3than5Big, bigger than2A small,5replace3.ltsfor[2， 3]
  • In the sixth loop, the element is7
    • Due to the7than3Student: big, so I’m just going to7Add to the end of the array,ltsfor[2, 3, 7)
  • On the seventh loop, the element is101
    • Due to the101than7Student: big, so I’m just going to101Add to the end of the array,ltsfor[2, 3, 7, 101]
  • In the eighth cycle, the element is18
    • Due to the18than7Big, bigger than101A small,101replace18.ltsfor18], [2, 3, 7,
  • In the ninth loop, the element is20
    • Due to the20than18Student: big, so I’m just going to20Add to the end of the array,ltsfor[2, 3, 7, 18, 20]

After completing the loop, you will find that the length of the LTS array is 5, and you can return 5 directly.

The specific code part here is not much to repeat, because it is really difficult to think of, when asked should not think of this binary search method, 👇 put a link, for reference: [here](




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ