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

 

풀이

 

i번째 수의 가장 긴 증가하는 부분 수열 길이는

1. 1~i-1번째 중 i보다 값이 작으면서

2. 가장 긴 증가하는 부분 수열의 길이가 max인 값

보다 1이 크다.

 

중간에 max=0을 안해주고 계속 반복문 돌렸더니 오류가 발생함. 주의해야겠다.

 

 

코드

#include <stdio.h>
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int numArr[1001],data[1001];
    int maxNum;
    int n;
    scanf("%d", &n);
    
    for(int i=1;i<=n;i++){
        scanf("%d", &data[i]);
    }
    for(int i=1;i<=n;i++){
        numArr[i]=1;
    }
    
    for(int i=2;i<=n;i++){
        maxNum=0;
        for(int j=1;j<i;j++){
            if(data[j]<data[i]) {
                maxNum=max(maxNum, numArr[j]);
                numArr[i]=maxNum+1;
            }
        }
        
    }
    
    int answer = 0;
    
    for(int i=1;i<=n;i++){
        answer=max(numArr[i],answer);
    }
    
    printf("%d", answer);
    
}