위 문제는 백준 사이트의 알고리즘 11053 문제에 관한 설명입니다.

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

초기에 작성했던 코드

 
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();
		int A[] = new int[length];
		int dp[] = new int[length];
		for(int i = 0 ; i < length; i++)
			A[i] = scanner.nextInt();

		for(int i = 0 ; i < length; i++)
		{
			dp[i]=1;
			for(int j = 0; j < i; j++)
			{
				if(A[j]<A[i]&&dp[i]<=dp[j])
					dp[i]= dp[j]+1;
			}
		}
		Arrays.sort(dp);
		System.out.println(dp[length-1]);
		
	}
}

10 20 10 30 20 50 이면

dp[1] (20)은 10 20으로 2이고

dp[3] (30)은 10 20 30으로 3이다.

dp[0] (10)도 10으로 숫자가 있기 때문에 1로 초기화 합니다.

반복문 2개로 수열[i]보다 작은 범위의 수열[j]를 훑어서 수열[i]보다 값이 작으면서

dp[j]가 dp[i]보다 값이 크거나 같다면,

dp[i] = dp[j]+1 을 해줍니다.

가장 긴 증가하는 수열