[BOJ] 11053 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053

예전에 이해를 못했던 가장 긴 증가하는 부분수열이다. 이 문제는 이미 파이썬으로 풀어봤어서 Java로 풀어보려고 한다.

Python

n = int(input())

seq = list(map(int, input().split()))

next = [1] * n

ans = 0

for i in range(n):
  for j in range(i+1, n):
    if seq[i] < seq[j]:
      next[j] = max(next[j], next[i] + 1)
      
print(max(next))

next라는 배열을 1로 초기화 시켰다. 해당 요소만 포함하는 부분 수열의 길이를 정의했다.

그러고 나서 2중 for문을 돌면서 i를 기준으로 seq[i]보다 큰 원소인 seq[j]를 만나게 되면 next[i]라는 부분수열에 seq[j]를 포함시킨다는 의미로 1을 더해주고, 기존 next[j]의 길이와 비교해서 더 긴 값을 저장시켰다.

이렇게 함으로써 가장 긴 증가하는 부분 수열의 길이를 구할 수 있게 된다.

Java

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

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int length = scanner.nextInt();
        ArrayList<Integer> nums = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            nums.add(scanner.nextInt());
        }

        int[] next = new int[length];

        Arrays.fill(next, 1);

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (nums.get(i) < nums.get(j)) {
                    next[j] = Math.max(next[i] + 1, next[j]);
                }
            }
        }

        System.out.println(Arrays.stream(next).max().getAsInt());
        scanner.close();
    }
}