11053

가장 긴 증가하는 부분 수열

 

answer 초기화 안하면 실패한다..

 

import java.util.Arrays;
import java.util.Scanner;

class Main {

	static int N;
	static int  answer;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int [] arr = new int[1001];
		int [] dp = new int[1001];
		
		for (int i = 0 ; i < N ; ++i )
			arr[i] = in.nextInt();
		
		//answer 초기화 안하면 TC에서 fail 발생하는 경우가 생김.
		dp[0]=1;
		answer=dp[0];
		
		for ( int i = 1; i < N; ++i) {
			//dp[i] = 1; // 여기서 초기화하면 max를 나중에 순회하면서 찾아야되서 귀찮음.
			for  (int j = i -1 ; j >= 0 ;  --j ) {
				if ( arr[j] < arr[i] && dp[i] < dp[j] )	
					dp[i] = dp[j];
			}
			++dp[i]; //종전 최대값에 +1을 해줘야함... 조건에 맞지 않는 경우? 초기값이 0이므로 자연스럽게 1이된다.
			answer = Math.max(dp[i], answer);
		}

		System.out.println(answer);
	}
}

ex)
6 
3 4 5 1 6 2
1 2 3 1 4 2 
4