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

思路：

• 动态规划，每个位置都要向前遍历寻找以当前字符结尾的最长子序列长度
• 思路2，维护一个递增的数组，若当前元素的值大于前一个值，则加入数组尾部，否则找到该元素在递增数组中的位置，替换原数组位置的元素注意这种替换不会改变最长数组的长度，若后面部分的递增数组大于前面，都替换前面后后面必然还有剩余可以加入数组的元素，这是数组长度必然会增加，若后面递增子序列小于前面，因为只是替换，所以结果还是前面部分的长度但有一个点需要注意，需要实时记录数组的尾部，用尾部索引代表长度

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        //思路2，维护一个递增的数组，若当前元素的值大于前一个值，则加入数组尾部，否则找到该元素在递增数组中的位置，替换原数组位置的元素
        //注意这种替换不会改变最长数组的长度，若后面部分的递增数组大于前面，都替换前面后后面必然还有剩余可以加入数组的元素，这是数组长度必然会增加，若后面递增子序列小于前面，因为只是替换，所以结果还是前面部分的长度
        //但有一个点需要注意，需要实时记录数组的尾部，用尾部索引代表长度
        if(arr==null||arr.length==0){
            return 0;
        }
        int n=arr.length;
        int res=0;
        int[] nums=new int[n];
        int end=-1;
        for(int i=0;i<n;i++){
            if(i==0||arr[i]>nums[end]){
                nums[++end]=arr[i];
            }else{
                int index=binarySearch(nums,end,arr[i]);
                nums[index]=arr[i];
            }
        }
        return end+1;
        
//         //动态规划，每个位置都要向前遍历寻找以当前字符结尾的最长子序列长度
//         if(arr==null||arr.length==0){
//             return 0;
//         }
//         int n=arr.length;
//         int res=0;
//         int[] dp=new int[n];
//         Arrays.fill(dp,1);
//         for(int i=1;i<n;i++){
//             int temp=arr[i];
//             for(int j=i-1;j>=0;j--){
//                 if(temp>arr[j]){
//                     dp[i]=Math.max(dp[i],dp[j]+1);
//                 }
//             }
//             res=Math.max(res,dp[i]);
//         }
//         return res;
    }
    private int binarySearch(int[] nums,int end,int target){
        if(nums==null||end<0){
            return -1;
        }
        int left=0,right=end;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
}