[JAVA] 백준 11053번 가장 긴 증가하는 부분 수열

링크

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

풀이

✅ LIS 최장증가수열 문제
DP로 푼다면 시간복잡도 O(N2)
반복문을 이용한 Bottom-Up 방식으로 풀었는데
재귀로 푼 방법도 아래 링크에서 확인했다
참고: https://st-lab.tistory.com/137

코드

 import java.util.*;
class Main {
  public static void main(String[] args) {
    Main T = new Main();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    int[] dp = new int[n];//dp[i]는 arr[i]가 최장증가수열의 가장 마지막 원소일 경우, 최대길이

    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    int ans = 1;
    dp[0] = 1; //dp 처음은 최소길이로 초기화
    for (int i = 1; i < n; i++) {
      int max = 0;
      for (int j = i - 1; j >= 0; j--) { //앞에 있는 원소들 중 arr[i]의 값보다 작으면서 dp최대값 +1
        if(arr[j] < arr[i] && dp[j] > max) max = dp[j];
      }
      dp[i] = max + 1; //기존의 자리값
      ans = Math.max(ans, dp[i]);
    }
    System.out.println(ans);
  }
}