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

이번 문제는 11053과 다르게 가장 긴 수열의 길이를 찾는 게 아닌 증가하는 수열들 중에서 가장 큰 합을 가지는 부분 수열을 찾는 문제이다.

 

11053에서 찾은 새로운 방법(이진 탐색)으로 합을 찾아보려고 했지만.. 할 수 없는 건지 실력이 부족한 건지 풀 수가 없었다. ㅠㅠ

더 공부한 후에 다시 도전해 봐야지

 

그래서 결국 DP를 이용하여 문제를 해결했다.

 

11053에서 DP를 이용한 방법과 아주 유사하다.

앞선 문제에서는 dp 배열에 길이를 저장했다면 이번 문제에서는 dp 배열에 원소의 합을 저장해 주면 된다.

 

□ 소스코드

void best11055(){
    int n;
    scanf("%d",&n);
    
    int array[1001] = {0};
    int dp[1001] = {0};
    
    for(int i=1;i<=n;i++)
        scanf("%d",&array[i]);
    
    int res = 0;
    for(int i=1;i<=n;i++){
        dp[i] = array[i];
        for(int j=1; j<i; j++){
            if(array[j] < array[i] && dp[i] < dp[j] + array[i]){
                dp[i] = dp[j] + array[i];
            }
        }
        res = max(res, dp[i]);
    }
    printf("%d\n",res);
}