백준 11055번
https://www.acmicpc.net/problem/11055
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
에 저장하는 것이기 때문에 첫 번째 max
는 arr[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