[백준] 11055번 : 가장 큰 증가하는 수열 - JAVA [자바]

https://www.acmicpc.net/problem/11055

i 번째 숫자에서 가장 큰 합을 지닌 수열을 만드려면

1. i 번째보다 왼쪽에 있는 숫자들 중에 i 번째 수보다 작은 수가 있는지 본다.
2. 작은 수가 있을 때, 이 수에 i 번째 수가 붙어서 만든 수열을 본다.
3. 만들어진 수열의 합과 i 번째 수가 가지고 있는 수열의 합을 비교한다.
4. 합이 더 커지면 i 번째 수의 수열을 바꾼다.

public class bj11055 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 숫자 입력
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        
        // 숫자들 배열
        int[] arr = new int[N + 1];
        
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 각 숫자의 수열의 합
        int[] dp = new int[N + 1];
        
        // 가장 첫번째에 있는 숫자가 만들 수 있는 수열은 자기 자신만 포함하는 수열이다.
        // 이 수열의 합은 자기 자신이다.
        dp[1] = arr[1];

        // 내 왼쪽에 나보다 더 작은 수가 있다
        // 그 수에 내가 붙어서 수열을 만들었을 때의 합이 더 큰가를 생각한다.
        // 2 번째 수부터 N 번째 수까지 반복한다
        for (int i = 2; i < N + 1; i++) {
            // 가장 초기의 수열은 자기 자신이다
            // 그 수열의 합은 자기 자신이다.
            dp[i] = arr[i];
            // i 번째 보다 왼쪽에 있는 숫자를 본다.
            for (int j = 1; j < i; j++) {
            	// 왼쪽에 있는 수가 i 번째 수보다 작다 -> 수열을 만들 수 있다
                if (arr[i] > arr[j]) {
                    // 그 전의 수열에 내가 붙어서 새로운 수열을 만들었을 때
                    // 그 수열의 합(dp[j] + arr[i])이 지금 내 수열의 합(dp[i])보다 크다.
                    if (dp[i] < dp[j] + arr[i]) {
                        dp[i] = dp[j] + arr[i];
                    }
                }
            }
        }


		// 만들어진 수열들의 합을 보면서 가장 큰 값을 출력한다.
        int answer = 0;
        for (int a : dp) {
            if (a > answer) {
                answer = a;
            }
        }
        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}