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

📝 Memo

Memory : 1984 KB

Time : 0 ms

🖥️ Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    int arr[1001];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    int dp[1001] = {0,};
    int max = -1;
    for(int i=0;i<n;i++){
        dp[i] = arr[i];
        for(int j = 0;j<=i;j++){
            if(arr[j] < arr[i]){
                dp[i] = (dp[i] > dp[j]+arr[i])?dp[i]:dp[j]+arr[i];
            }
        }
    }
    for(int i=0;i<n;i++){
        max = (max<dp[i])?dp[i]:max;
    }
    printf("%d",max);
}