[백준] 11055번 : 가장 큰 증가하는 부분 수열

문제

 

 

접근 방식

수열 {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이 주어졌을 때 1, 100, 2, 60, 50 처럼

들쑥날쑥한 부분 수열이 아닌 1, 2, 50, 60 처럼 증가하는 부분 수열 중에서

합이 가장 큰 부분 수열을 구해야 하는 문제다.

 

우선 간단하게 생각해보면 이전 수보다 큰 값이 나올 때까지 모두 합해주면

특정 수로 끝나는 부분 수열의 합을 구할 수는 있다.

1로 끝나는 부분 수열은 {1} = 1

1 > 100 > 2 (이전 수인 100보다 작음)
== 100으로 끝나는 부분 수열은 {1, 100} = 101

2 > 50 > 60 > 3 (이전 수인 60보다 작음)
== 60으로 끝나는 부분 수열은 {2, 50, 60} = 112

 

위와 같이 특정 수로 끝나는 부분 수열의 값을 알 수 있지만

문제에서 요구하는 부분 수열과는 조금 다르다.

 

문제에서는 {1, 2, 50, 60} = 113 처럼 연속된 부분 수열이 아니라도

값이 증가하기만 한다면 부분 수열로 만들 수 있기 때문에

{1, 2, 50, 60} 과 같은 수열을 만들기 위해서는

{1}과 {2, 50, 60}을 합치면 된다는 것을 알 수 있다.

 

즉, 60으로 끝나는 부분 수열의 합은

60보다 작은 부분 수열의 합들을 더한 값이 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		int[] arr = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int max = arr[0];
		int[] dp = new int[n];
		dp[0] = arr[0];

		for (int i = 1; i < n; i++) {
			dp[i] = arr[i];
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					dp[i] = Math.max(dp[j] + arr[i], dp[i]);
				}
			}

			max = Math.max(max, dp[i]);
		}

		System.out.println(max);
	}
}