[Java] 11055. 가장 큰 증가하는 부분 수열

점화식

 

• 초기 상태
  • 각 원소는 그 자체로 하나의 증가 부분 수열을 형성합니다.
  • 따라서 초기값:dp[i]=A[i](최소 합은 자기 자신)
• 상태 전이
  • 인덱스 ii에서 가능한 이전 원소 jj를 탐색합니다:dp[i]=max⁡(dp[i], dp[j]+A[i]) (for all j<i and A[j]<A[i])
  • dp[j]+A[i]: A[j]를 포함한 증가 부분 수열에 A[i]A[i]를 추가한 경우의 합.
• 최종 결과
  • 모든 ii에 대해 dp[i]를 계산한 후:최대 합=max⁡(dp[0],dp[1],…,dp[n−1])

 

 

코드

import java.io.*;

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[] array = new int[n];
        int[] dp = new int[n];
        
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(input[i]);
            dp[i] = array[i];
        }
        
        for (int i = 1; i < n; i++) {
        	for (int j = 0; j < i; j++) {
        		if (array[j] < array[i]) {
        			dp[i] = Math.max(dp[i], array[i] + dp[j]);
        		}
        	}
        }
        
        int maxValue = 0;
        for (int i = 0; i < n; i++) {
        	maxValue = Math.max(maxValue, dp[i]);
        }

        System.out.println(maxValue);
    }
}

import java.io.*;

public class Main {	
    public static int[] array;
    public static int[] dp;
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        n = Integer.parseInt(br.readLine());
        array = new int[n];
        dp = new int[n];
        
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            array[i] = Integer.parseInt(input[i]);
            dp[i] = -1;
        }
        
        int maxSum = 0;
        for (int i = 0; i < n; i++) {
            maxSum = Math.max(maxSum, findMaxSum(i));
        }

        System.out.println(maxSum);
    }
    
    public static int findMaxSum(int index) {
        if (dp[index] != -1) {
            return dp[index];
        }

        int maxSum = array[index];
        for (int next = index + 1; next < n; next++) {
            if (array[next] > array[index]) {
                maxSum = Math.max(maxSum, array[index] + findMaxSum(next));
            }
        }

        dp[index] = maxSum;
        return maxSum;
    }
}