[백준(baekjoon) 11055] 가장 큰 증가 부분 수열

문제

백준 11055

n(1…1,000)과 n의 크기를 가진 수열이 주어질 때,
수열에서 증가하는 부분 수열 중 가장 큰 합을 출력.

• 예시 : A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우, A = {1, 2, 50, 60} 이고 합은 113이다.

해결

가장 긴 증가하는 부분과 매우 유사한 문제이다.
이것도 마찬가지로! 2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다.
최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다.
그러므로 일일이 구한 후 MAX 값을 찾아내면 끝!

알고리즘

DP로 풀었고, bottom-up 방식으로만 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int[][] input = new int[n][2]; // 0 : vaule, 1 : sum
9.        int max = 0;
10.
11.        for (int i = 0; i < n; i++) {
12.            int vaule = sc.nextInt();
13.            input[i][0] = vaule;
14.            input[i][1] = vaule;
15.            for (int j = 0; j < i; j++) {
16.                if (vaule > input[j][0])
17.                    input[i][1] = Math.max(input[i][1], input[j][1] + vaule);
18.            }
19.            max = max < input[i][1] ? input[i][1] : max;
20.        }
21.        System.out.println(max);
22.    }
23.}

결과