백준 11055번 가장 큰 증가하는 부분 수열 Java

: ) YOUNG·2024년 3월 29일
1

알고리즘

목록 보기
341/417
post-thumbnail

백준 11055번
https://www.acmicpc.net/problem/11055

문제



생각하기


  • LIS인데 하나의 조건이 추가됐음
    • 가장 합이 크게되는 LIS 찾기


동작


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

기존에 있던 LIS에서 합을 memo 에 저장하는 것이기 때문에 첫 번째 maxarr[n] 자신이 된다.



결과


코드



import java.io.*;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr, memo;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, LIS(i));
        }

        sb.append(max);
        return sb.toString();
    } // End of solve()

    private static int LIS(int n) {

        if (memo[n] != -1) return memo[n];

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

        memo[n] = max;
        return memo[n];
    } // End of LIS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        arr = new int[N];
        memo = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            memo[i] = -1;
        }
    } // End of input()
} // End of Main class

0개의 댓글