[알고리즘] 백준 - 11053 ( 가장 긴 증가하는 부분 수열 ) / 자바

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] dp = new int[N];

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

		
		dp[0] = 1;
		int maxIndex;
		int maxValue;
		for (int i = 1; i < N; i++) {
			if (arr[i] == arr[i - 1]) {
				dp[i] = dp[i - 1];
			} else {
				maxIndex = -1;
				maxValue = 1;
				for (int j = i - 1; j >= 0; j--) {
					//현재 값보다 작고 길이가 긴 인덱스를 찾음
					if (arr[j] < arr[i] && maxValue <= dp[j]) {
						maxValue = dp[j];
						maxIndex = j;
					}
				}
				// 자신보다 작은 값이 없으면 1을 , 있으면 가장 큰 길이를 가지는 값에 +1
				dp[i] = maxIndex == -1 ? 1 : dp[maxIndex] + 1;

			}
		}
		
		maxValue = 0;
		for (int i = 0; i < N; i++) {
			maxValue = maxValue > dp[i] ? maxValue : dp[i];
		}
		System.out.print(maxValue);
	}
}