leetcode 300. Longest increasing subsequence (medium)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/longest-increasing-subsequence

Give you an array of integers  nums , Find the length of the longest strictly increasing subsequence .

Subsequence   Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7]  It's an array  [0,3,1,6,2,2,7]  The subsequence .

Example  1：

Input ：nums = [10,9,2,5,3,7,101,18] Output ：4 explain ： The longest increasing subsequence is  [2,3,7,101], So the length is  4 .

Example  2：

Input ：nums = [0,1,0,3,2,3] Output ：4

Example  3：

Input ：nums = [7,7,7,7,7,7,7] Output ：1

Tips ：

• 1 <= nums.length <= 2500

• -104 <= nums[i] <= 104

Advanced ：

• You can reduce the time complexity of the algorithm to &nbsp;O(n log(n))  Do you ?

Two 、 Their thinking

The core idea is to use an array dp To preserve ,dp[i] Is the longest increasing subsequence up to this position . Finally, find the maximum value of all positions , instead of dp The last element of .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int lengthOfLIS(int[] nums) {
 int n = nums.length;
 if (n <= 1) {
 return n;
 }
 int[] dp = new int[n];
 for (int i = 0; i < n; i++) {
 dp[i] = 1;
 }
 int ret = dp[0];
 for (int i = 0; i < n; i++) {
 for (int j = 0; j < i; j++) {
 if (nums[i] > nums[j]) {
 dp[i] = Math.max(dp[i], dp[j] + 1);
 }
 }
 ret = Math.max(dp[i], ret);
 }
 return ret;
 }
}


Four 、 Summary notes

• 2022/6/25  It will rain heavily in the next two days