300. Longest increasing subsequence

---

subject

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 .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-increasing-subsequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

One 、O(n²) Solution

Dynamic programming , Model from left to right

dp[i] Subsequence must be i At the end of the number of positions , How long is the longest increasing subsequence ? Whole middle demand max That's the answer.
Every time dp[i] when , Traversal array 0 To i-1, Find out the ratio nums[i] The position of a small number j,
dp[i]=Math.max(dp[i],dp[j]+1);

Code

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        int n=nums.length;
        if(n==0){
    
            return 0;
        }
        int max=1;
        int[] dp=new int[n];
        dp[0]=1;
        for(int i=1;i<n;i++){
    
            dp[i]=1;
            for(int 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;
    }
}

Optimal solution

auxiliary end Array
end[i]: At present, all lengths are i+ 1 The smallest ending in the increasing subsequence of

How to fill in end?
One number at a time num[i], With two points in end The leftmost greater than... Is found in the array num[i] The location of j
end[j]=num[i];
If not greater than num[i] Number of numbers , be end[j+1]=num[i]

After you put in a value , The position meaning of rewriting is right , The position that has not been rewritten continues to ensure the correct meaning

	public static int lengthOfLIS(int[] arr) {
    
		if (arr == null || arr.length == 0) {
    
			return 0;
		}
		int[] ends = new int[arr.length];
		ends[0] = arr[0];
		int right = 0;
		int l = 0;
		int r = 0;
		int m = 0;
		int max = 1;
		for (int i = 1; i < arr.length; i++) {
    
			l = 0;
			r = right;
			while (l <= r) {
    
				m = (l + r) / 2;
				if (arr[i] > ends[m]) {
    
					l = m + 1;
				} else {
    
					r = m - 1;
				}
			}
			right = Math.max(right, l);
			ends[l] = arr[i];
			max = Math.max(max, l + 1);
		}
		return max;
	}