算法--2023.1.23

1.力扣300--最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        //贪心算法，基本思路：dp数组维护长度为下表i的最长子序列的最后一个值的最小数
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[1] = nums[0];
        int len = 1;
        for(int i = 1;i<n;i++){
            //遍历数组中的每一个元素，如果该元素比当前最长长度的最后一个值要大，我们把将最长长度加一，把这个值放在最后
            if(nums[i]>dp[len]){
                dp[++len] = nums[i];
                //System.out.println(dp[len]);
            //否则我们在dp这个数组中找到一个最大的但比nums[i]小的值，然后更新dp数组中后面的一个值，表示dp[pos+1]结尾的最小值为这个    
            }else{

                //这里采用二分查找，会存在一个特殊情况，所有值都比nums[i]大，所以这里采用pos变量解决
                int start = 1, end = len, mid = 0,target = nums[i], pos = 0;
                while(start<=end){
                    mid = (start+end)/2;
                    //System.out.println(mid);
                    if(dp[mid]<target){
                        pos = mid;
                        start = mid+1;
                    }else{
                        end = mid-1;
                    }
                }
                dp[pos+1] = target;
                System.out.println(start+1);
            }
        }
        return len;
    }
}