Q2352. 반도체 설계

LIS입니다.

아래와 같이 구현했으나, 메모리 초과로 해당 알고리즘은 불가능했네요.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q2352 { static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num = Integer.parseInt(st.nextToken()); dp = new int[2][num+1]; st = new StringTokenizer(br.readLine()); for (int i = 1; i <= num; i++) { dp[0][i] = Integer.parseInt(st.nextToken()); } for (int i = 1; i < num; i++) { int min = 0; int nowNum = dp[0][i]; for (int j = i+1; j <= num; j++) { if (nowNum < dp[0][j]) { if (min == 0 || min > dp[0][j]){ min = dp[0][j]; dp[1][j] = Math.max(dp[1][j], dp[1][i] + 1); } } } } int maxValue = 0; for (int i = 1; i <= num; i++) { maxValue = Math.max(maxValue, dp[1][i]); } maxValue += 1; System.out.println(maxValue); } }