11053번) 가장 긴 증가하는 부분 수열

문제 출처 : https://www.acmicpc.net/problem/11053

import java.util.Scanner; public class Q11053 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int input = scanner.nextInt(); int[][] array = new int[input][2]; //0번째 -> input 값, 1번째 -> 증가 부분 수열의 길 for ( int i = 0; i < input; i++ ) { array[i][0] = scanner.nextInt(); //for문을 거꾸로 돌려야 if문을 그나마 적게 수행 for ( int j = i-1; j >= 0; j-- ) { //증가 부분 수열이면서, 현재까지 증가 부분 수열의 길이가 클 경우 if ( array[j][0] < array[i][0] && array[i][1] < array[j][1] ) { array[i][1] = array[j][1]; } } array[i][1] += 1; } scanner.close(); //가장 긴 증가 부분 수열 길이 찾기 int max = 0; for ( int i = 0; i < input; i++ ) { max = max > array[i][1] ? max : array[i][1]; } System.out.println(max); } }