[백준 11055] 가장 큰 증가 부분 수열

 

가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열과 로직이 똑같은 문제이다.

 

수열의 길이가 아닌 각 수열의 합을 dp 배열에 담으면 된다.

 

 

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[n];
        int dp[] = new int[n];
        
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int max = 0;
        for(int i=0; i<n; i++) {
            dp[i] = a[i];
            for(int j=0; j<i; j++) {
                if(a[i] > a[j] && dp[i] < dp[j] + a[i])
                    dp[i] = dp[j] + a[i];
            }
            if(max < dp[i])
                max = dp[i];
        }
        
        System.out.println(max);
        sc.close();
}