[DP]300. Longest Increasing Subsequence 최장 증가 하위 시퀀스(Binary Search DP)

300. Longest Increasing Subsequence
제목: 원숭이가 산을 내려오고 산을 내려오는 길을 따라 복숭아나무가 줄지어 있고 나무마다 복숭아가 맺혀 있다.원숭이가 복숭아를 따려고 하지만 또 다른 조건을 지켜야 한다. 마른 사람은 산을 내려가는 방향만 따라갈 수 있고 고개를 돌릴 수 없다. 나무마다 최대 한 그루씩 따야 한다. 그리고 나무의 복숭아를 따면 이 나무보다 복숭아가 적은 나무의 복숭아를 따면 안 된다. 그러면 원숭이는 최대 몇 과까지 따야 하는가?거리설명, 예를 들어 다섯 그루의 나무가 있는데 각각 10, 4, 5, 12, 8그루의 복숭아가 열렸다. 그러면 작은 원숭이는 최대 3개의 복숭아를 딸 수 있다. 4, 5, 12개의 복숭아가 열린 복숭아나무에서 나온 것이다.
감사 futurehau 대신의 우수한 해석: 링크
O(nlog(n))
알고리즘 프로세스: 하나의 그룹 h를 사용하고 먼저 h[0]=arr[0]를 사용합니다.이미 부여된 h의 앞부분을 질서구역으로 기억하고 질서구역만 고찰합니다.뒤로 옮겨다니며 arr[i]에 대해 h의 질서 구역에서 arr[i]보다 큰 첫 번째 위치를 찾습니다.찾으면 그 위치의 값을arr[i]로 업데이트합니다. 그렇지 않으면 h의 질서구 길이가 1이 증가하고 새로 추가된 위치의값은arr[i]입니다.2분으로 위치를 찾습니다. 상술한 과정에서 위치 0에서arr[i]까지의 업데이트 위치의 요소 개수는 arr[i]로 끝나는 가장 긴 점차적 서열의 길이입니다.2분에서 찾아낸 위치를 보면 이 길이를 알 수 있다.전역 변수를 사용하여 max에서 업데이트된 최장 증자 서열의 길이를 저장합니다.
알고리즘 원리: •h[i]는 현재 시간까지 반복되고 길이가 i+1의 최장 증자 서열의 최소 끝을 나타낸다.이렇게 해서 사실 우리가 매번 하는 일은 가장 긴 점증자 서열의 길이를 늘리든지, 아니면 길이가 변하지 않든지 하는 것이다. 그러나 모든 길이에 대응하는 가장 작은 끝을 갱신하는 것이다. 이것은 나중에 길이를 확장하는 데 유리하다. 왜냐하면 너는 더욱 작기 때문이다. 내 후반의 요소는 너보다 더 크기 쉽다.이렇게 하면 사실 마지막 h의 유효구역 길이는 구하는 것이지만 더 이상 반복하지 않기 위해 중도에 하나의 max를 사용하여 현재 위치의 가장 긴 점차적 서열을 기록하고 max를 업데이트하면 된다.n회를 했고 매번 2분마다 위치log(n)를 찾았기 때문에 복잡도는 n(logn)이다.

public int lengthOfLIS(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        int[] h=new int[nums.length];
        h[0]=nums[0];
        int max=0;//           
        for(int i=1;ih[max]){
                h[++max]=nums[i];
                continue;
            }
            else{
                int pos=findFirstBigger(h,0,max,nums[i]);
                h[pos]=nums[i];
            }
        }
        return max+1;
    }
    public int findFirstBigger(int[] h,int left,int right,int target){
        if(left==right)
            return left;
        int mid=(left+right)/2;
        if(h[mid]