Longest Increasing Sequence(LIS) 정답 코드

문제를 보시려면 여기를 클릭

이하는 코드입니다.

#include <stdio.h>
#include <queue>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int number;
    int length;
} Cache;
 
struct Compare {
    bool operator() (Cache left, Cache right) {
        return left.length < right.length;
    }
};
 
int N;
int board[501];
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d", &N);
 
        priority_queue<Cache, vector<Cache>, Compare> maxHeap;
        for (int j = 0; j < N; j++) {
            scanf("%d", &board[j]);
            vector<Cache> temp;
            bool found = false;
            while (maxHeap.size() > 0) {
                Cache item = maxHeap.top();
                if (item.number < board[j]) {
                    Cache *newItem = new Cache;
 
                    newItem->number = board[j];
                    newItem->length = item.length + 1;
 
                    maxHeap.push(*newItem);
                    found = true;
                    break;
                }
                temp.push_back(item);
                maxHeap.pop();
            }
 
            // 
            if (!found) {
                Cache *newItem = new Cache;
 
                newItem->number = board[j];
                newItem->length = 1;
 
                maxHeap.push(*newItem);
            }
 
            //
            for (int k = 0; k < temp.size(); k++) {
                maxHeap.push(temp.at(k));
            }
        }
 
        printf("%d\n", maxHeap.top().length);
    }
 
    return 0;
}