[백준] 11055번 가장 큰 증가 부분 수열 자바

문제

 

11055번: 가장 큰 증가 부분 수열

 

 

문제 풀이

 

구글링했다. 역시 DP는 너무 어려워.. 어떻게 이런 방법으로 풀 생각을 하지 라고 생각했다..

 

알고리즘은 반복문을 돌면서 dp배열에 현재 인덱스까지의 최대 배열 합을 갱신해나가면서 배열을 채우고 가장 큰 값을 반환하면 되는 거였다.

 

코드에서 의문이었던 점은 현재 i번째의 배열 값과 그 전까지의(j) 배열 값들을 확인하는 반복문에서 i까지의 값이 증가되는 것을 확인하지 않고 그 j의 값 자체가 i값보다 작으면 바로 dp를 갱신하는 거였는데, dp에 담긴 값은 어차피 그 때까지의 최대 부분 수열 합이므로 A[i] > A[j]이면 그 dp[j]의 값은 i값보다 다 작은 수들이 담겨있기 때문에 현재 값과 dp값을 합하여 계속 비교해 나가면 된다. 

 

 

 

소스 코드

 

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int A[] = new int[N+1];
		int dp[] = new int[N+1];
		
		for(int i = 1; i <= N; i++)
			A[i] = sc.nextInt();
		
		dp[1] = A[1];
		for(int i = 2; i <= N; i++) {
			dp[i] = A[i];
			for(int j = 1; j < i; j++)
				if(A[i] > A[j])
					dp[i] = Math.max(dp[i], dp[j] + A[i]);
		}
		
		int ans = 0;
		for(int i = 1; i <= N; i++) {
			if(dp[i] > ans)
				ans = dp[i];
		}
		
		System.out.println(ans);
		sc.close();
	}

}