0%

[백준/11055] 가장 큰 증가 부분 수열

작성일 Edited on In Disqus:

Baekjoon Online Judge - 11055

Review

  • 백준 11053 문제랑 비슷…
  • 하지만 DP[i] < DP[j] + A[i]를 만족하는 경우에만 최대값이 될 수 있다.
  • 이 부분을 몰라서 네 번이나 틀림.

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  
  public static void main(String args[]) throws IOException{
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());
    int[] A = new int[N + 1];
    int[] DP = new int[N + 1];
    int ans = 0;
    StringTokenizer st = new StringTokenizer(bf.readLine());
    
    for(int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    
    for(int i = 1; i <= N; i++ ) {
      DP[i] = A[i];
      for(int j = 1; j < i; j++) {
        if(A[i] > A[j] && DP[i] < DP[j]+A[i]) {
          DP[i] = DP[j] + A[i];
        }
      }
      if(ans < DP[i]) {
        ans = DP[i];
      }
      
    }
    
    System.out.println(ans);
    
  }
  
}