11055

가장 큰 증가부분 수열

 

 

dp[i]=dp[i-1]

if arr[j]<arr[i]

    dp[i] = Math.max(dp[i], dp[j] + arr[i])

 

이 문제에는 DP(K-max)는 사용 불가. (엑셀 참조)

11055_가장큰증가부분수열.xlsx

0.01MB

 

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

class Main {

	static int N;
	static int answer;

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] arr = new int[1001];
		int[] dp = new int[1001];

		for (int i = 0; i < N; ++i)
			arr[i] = in.nextInt();

		dp[0] = arr[0];
		//초기화 잊지마라 루프에서 안챙겨준다.
		answer = dp[0];
		for (int i = 1; i < N; ++i) {
			dp[i]=arr[i];//최소값은 자기 자신
			for (int j = i - 1; j >= 0; --j) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[i], dp[j] + arr[i]);
				}
				answer = Math.max(dp[i], answer);					
			}			
		}
		
		/*
		for (int i = 0; i < N; i++) {
			System.out.printf("[%d %d] ", i, dp[i]);
		}
		System.out.println();*/
		
	
		System.out.println(answer);
	}
}

ex)
10
1000 100 2 50 60 3 5 6 7 8
[0 1000] [1 100] [2 2] [3 52] [4 112] [5 5] [6 10] [7 16] [8 23] [9 31] 
1000