최대 부분 증가수열(Dynamic Programing)

최대 부 증가수열

 

 

 

코드

package dynamic;

import javax.imageio.metadata.IIOMetadataFormatImpl;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 최대 부분 증가 수열
 */
public class Dynamic2 {
    static int[] dy;

    static int solution(int[] arr) {
        int answer = 0;
        dy = new int[arr.length];

        dy[0] = 1;

        for (int i = 1; i < arr.length; i++) {
            int max = 0;
            
			// i 번째 앞 탐색
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i] && dy[j] > max) max = dy[j];
            }
            dy[i] = max + 1; // 없을 경우 0 + 1 로 = 1
            answer = Math.max(answer, dy[i]); // 최대값 저장
        }
        return answer;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(solution(arr));


    }
}