티스토리 뷰

728x90

https://www.acmicpc.net/problem/11055

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수�

www.acmicpc.net

동적계획법 C++

이번엔 가장 큰 증가하는 부분 수열의 합 구하기

 

접근 방법

지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다.

차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우

길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로

비교할 때 이 부분을 주의해야 했다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n ;

    int num[n];
    int max[n];
    int result = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
        max[i] = num[i];
        for(int j = 0 ; j < i ; j++){
            if(num[j] < num[i] && max[j]+num[i] >= max[i]){
                max[i] = max[j]+num[i];
            }
        }
        if(result < max[i])
            result = max[i];
    }
    
    cout << result;
    return 0;
}

 

728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함