题解 | #最长递增子序列#

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        // write code here
//         num记录每个数组能组成的最大序列；temp记录每个长度中最后一个位置的数字；
        int[] nums = new int[arr.length];
        int[] temp = new int[arr.length];
        nums[0] = 1;
        int tempindex = 0;
        temp[tempindex] = arr[0];
        if(arr.length==1) return arr;
        for(int i=1;i<arr.length;i++){
            int left=0,right=tempindex;
            if(arr[i]==temp[tempindex]){
                nums[i]=tempindex+1;
                continue;
            }
            if(arr[i]>temp[tempindex]){
                ++tempindex;
                nums[i]=tempindex+1;
                temp[tempindex]=arr[i];
            }else{
                while(left<=right){
                    int mid = (right+left)/2;
                    if(temp[mid]>arr[i]){
                        right=mid-1;
                    }else{
                        left=mid+1;
                    }
                    
                }
                temp[left]=arr[i];
                nums[i]=left+1;
            }
        }
        int[] res = new int[tempindex+1];
        for(int i=nums.length-1;i>=0;--i){
            if(nums[i]==tempindex+1){
                res[tempindex]=arr[i];
                --tempindex;
            }
        }
        return res;
        
    }
}