题解 | #最长上升子序列(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    //本题的最优解可以做到时间复杂度为O（NlogN），空间复杂度不变
    //普通方法也就是动规方法求dp数组的时候要用两个for循环，所以时间复杂度自然为N²
    //最优解在求dp数组的时候利用二分法就可以将时间复杂度降为NlogN
    //介绍一下基本思路首先申请一个同样大小的ends数组ends数组初始化ends[0]=arr[0]
    //ends数组的含义为ends[i]表示所有长度为i+1的递增子序列中末尾数最小的为ends[i]
    //定义一个有效范围变量right初始化为0，0到right为有效区域，right往后为无效区域
    //dp数组的含义不变,即为以arr[i]结尾的子序列长度最长为dp[i]
    public int f(int[]arr,int[]dp){
        int []ends=new int[arr.length];
        ends[0]=arr[0];
        int right=0;           int mid=0; 
        for(int i=1;i<arr.length;i++){//循环时间复杂度为O（N）
           int L=0;
           int R=right;
            while(L<=R){//二分查找时间复杂度为logN
                mid=(L+R)/2;
                if(ends[mid]<arr[i]){
                    L=mid+1;
                }
                else{
                    R=mid-1;//这里一定要写mid-1，不然会死循环，看了半个小时才看出来我心态崩了
                }
            }
            right=Math.max(right,L);//更新right
            ends[L]=arr[i];
            dp[i]=L+1;
        }
        return right+1;
    }
    public int LIS (int[] arr) {
        // write code here
        if(arr==null||arr.length==0){
            return 0;
        }      
        int []dp=new int[arr.length];
        dp[0]=1;      
        return f(arr,dp);
    }
}