[백준 / 실버2] 11055 가장 큰 증가 부분 수열 (Java)

Ilhwanee·2022년 8월 19일
0

코딩테스트

목록 보기
86/155

문제 보기



사용한 것

  • 증가 구간 중 최대 값을 찾기 위한 bottom-up


풀이 방법

  • num에 비교한 숫자를 저장하되 num보다 작은 값은 비교 X(이미 비교한 인덱스에 포함되어있음)


코드

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 = Stream.of(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = arr[i];

            int num = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j] && arr[j] > num) {
                    dp[i] = Math.max(arr[i] + dp[j], dp[i]);
                }
            }
        }

        int answer = dp[0];
        for(int i = 1; i < N; i++) {
            answer = Math.max(dp[i], answer);
        }

        System.out.println(answer);
    }
}


profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글