문제

풀이 방법

예를 들어 설명 하겠다

ㅁㅁㅁㅁㅁㅁㅁㅁㅁ20ㅁㅁㅁㅁㅁ

이런식으로 있으면

20앞에 있는 수중 20보다 작은 가장 가까운 수가 있을것이다.

그렇다면 20까지 왔을때 가장 긴 증가하는 수열의 길이는

20보다 작은 가장 가까운 수의 +1 이 된다.

예를들어

10 20 10 30 20 50

에서 30까지 왔을때 30을 포함하는 가장 긴 수열의 길이는 30보다 작은 수중 가장 큰 수인

20에 +1을 한것이다.

코드

#include <iostream>
using namespace std;

int main()
{
    int input;
    cin >> input;
    int arr[1001] = {0,};
    int dp[1001] = {0,};
    int i,j;
    int min=0;
    int maxv;
    int max=0;
    for (i = 0; i < input; i++) {
        cin >> arr[i];
        dp[i] = 0;
    }
    for (i = 0; i < input; i++) {
        min = 0;
        for (j = 0; j < i; j++) {
            if (arr[j] < arr[i] && min < dp[j]) {
                min = dp[j];
            }
        }
        dp[i] = min + 1;
        if (max < dp[i]) max = dp[i];
    }
    cout <<max;
    return 0;
}