최대길이증가수열

 

11053 제출시 반례가 있음

ex)

5 
2 3 4 1 5

4

아래 글 참조

https://easy16.tistory.com/335

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer;
	static int []dy;
	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);

		n = in.nextInt();
		int arr[] = new int[n];
		for ( int i = 0 ; i<n ; i++) {
			arr[i] = in.nextInt();
		}
		//n번째 인덱스에서 최대수열길이를 저장
		dy = new int[n];
		
		//첫번째는 자기 자신만 있으므로 1
		dy[0]=1;
		//이후에는 앞의 숫자들 중, 가장 수열의 길이가 긴 부분을 찾아 자기 자신의 길이 +1을 더하면 된다.
		
		for ( int i = 1 ; i < arr.length; i++) {
			int max=0;
			for ( int j=i-1 ; j >=0 ; j--) {				
				if( arr[j] < arr[i] && dy[j] > max) {
					//현재값보다 앞에 있는 수 중, 가장 큰 값을 찾고, 길이를 1증가시킨 값을 저장.
					max = dy[j];
				}
				dy[i] = max + 1;
				answer = Math.max(dy[i], answer);
			}

		}
		
		
		
		System.out.println(answer);
		
	

	}

}
ex)
input
8
5 3 7 8 6 2 9 4
output
4