(11055)(DP) 백준 가장 큰 증가 부분 수열

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

풀이

---

이중 포문을 이용해서  

if(arr[i]> arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);

if(dp[i] == 0 ) dp[i] = arr[i];  하고 

max 값을 지속적으로 비교해서 저장해 주면 끝이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
#define max(a,b) a>b ? a:b
 
int main() {
    int N;
    int arr[1001] = { 0 };
    int dp[1001] = { 0 };
    int cnt;
 
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    dp[1] = arr[1];
    cnt = arr[1];
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);
            if (dp[i] == 0) dp[i] = arr[i];
        }
        cnt = max(cnt, dp[i]);
    }
 
    printf("%d", cnt);
 
    return 0;
}