27. Longest increasing subsequence

300. The longest increasing subsequence

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

Subsequences are sequences derived from arrays , 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

DP

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

Greedy Algorithm 、 Two points search