[Java] LIS - 최장 증가 부분 수열

https://sskl660.tistory.com/89

[Java]최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

두 가지 방법이 있다.

1. 최장 증가 부분 수열의 길이만 구하는 방법 (이 수열의 원소는 알 수 없다)

2. 최장 증가 부분 수열 자체를 구하는 방법

 

물론 1이 2보다 빠르다

1은 이진 탐색을 사용해서 O(NlgN) 

2는 O(N^2)

 

1번

import java.util.*;
import java.io.*;

public class s2_11053_lis{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);

    static int[] dp, pp;
    static int n;
    public static void main(String[] args){
        n = fs.nextInt();
        dp = new int[n];
        pp = new int[n];
        for (int i=0;i<n;i++) pp[i] = fs.nextInt();
        
        int len = 0;
        for (int i=0;i<n;i++){
            int index = BS(pp[i], 0, len, len + 1);
            if (index == -1){
                dp[len++] = pp[i];
            }
            else{
                dp[index] = pp[i];
            }
        }

        pw.println(len);
        pw.close();
    }

	private static int BS(int num, int start, int end, int size) {
		int res = 0;
        while (start <= end){
            int mid = (start + end) / 2;

            if (num <= dp[mid]){
                res = mid;
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }

        if (start == size){
            return -1;
        }
        else{
            return res;
        }
	}

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

 

 

2번

import java.util.*;
import java.io.*;

public class Main{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);

    static int[] dp, pp;
    static int ans = 1;
    public static void main(String[] args){
        int n = fs.nextInt();
        dp = new int[n];
        pp = new int[n];
        for (int i=0;i<n;i++) pp[i] = fs.nextInt();
        
        for (int i=0;i<n;i++) solve(i);

        pw.println(ans);
        pw.close();
    }

    static void solve(int ptr){
        int max = 1;
        for (int i=0;i<ptr;i++){
            if (pp[i] < pp[ptr]){
                max = Math.max(max, dp[i] + 1);
            }
        }
        dp[ptr] = max;
        ans = Math.max(ans, max);
    }

//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}