[BOJ/C++]11055번 가장 큰 증가 부분 수열

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

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

---

문제

수열 A가 주어졌을 때 그 수열의 증가 부분 수열 중 합이 가장 큰 것을 출력하는 프로그램

 

풀이 과정

https://lionontheshore.tistory.com/38

[BOJ/C++]11053번 가장 긴 증가하는 부분수열

와 같은 방식으로 풀었다. 

j<i인 arr[j]<arr[i]에서 증가 부분 수열 합 중 최대값을 저장해 둔 dp[i]와 arr[i]+dp[j]를 비교해 큰 것을 dp[i]에 저장했다.\

 

소스코드

#include<iostream>
using namespace std;

int main(void){
    int n;cin>>n;
    int arr[n+1];
    int dp[n+1];

    for(int i=1;i<=n;i++)
        cin>>arr[i];
    
    int max_num=0;
    for(int i=1;i<=n;i++){
        dp[i]=arr[i];
        for(int j=i-1;j>0;j--){
            if(arr[j]<arr[i]){
                dp[i]=max(dp[i], arr[i]+dp[j]);
            }
        }
        max_num=max(max_num,dp[i]);
    }
    cout<<max_num<<endl;
}