DP [백준 11055번 가장 큰 증가하는 부분수열] -java-

지난 시간에 풀이하였던 가장 긴 증가하는 부분 수열과 아주 유사한 문제이다. 대신에 달라지는 점은 부분 수열의 길이가 아니라 부분 수열의 합이 가장 큰 것을 찾는다는 것이다. 

다이나믹 프로그래밍에서 항상 중요한 것은 dp배열에 어떤 값을 넣느냐이다. 이번 문제에서는 dp[i]는 numbers[i]가 마지막인 부분 수열의 합으로 정의한다. 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] numbers = new int[num+1];
        numbers[0]=0;
        int[] dp = new int[num+1];
        dp[0]=0;
        for(int i=1;i<=num;i++) {
            numbers[i]=sc.nextInt();
        }
        
        for(int i=1;i<=num;i++) {
            dp[i]=numbers[i];
            for(int j=1;j<i;j++) {
                if(numbers[i]>numbers[j]&&dp[i]<dp[j]+numbers[i]) {
                    dp[i]=dp[j]+numbers[i];
                }
            }
        }
        
        Arrays.sort(dp);
        System.out.println(dp[dp.length-1]);
        
 
    }
 
}