데일리썽

문제 제목 : 가장 긴 증가하는 부분 수열

난이도 : 하

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        ArrayList<Integer> a = new ArrayList<Integer>();
        int[] dp = new int[1000];
        
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a.get(i) > a.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }  

        System.out.println(result);
    }
}