ALGOSPOT LIS (Longest Increasing Sequence)

2020.02.18

algospot / LIS

풀이

1. 수열이 맨 왼쪽부터 하나씩 들어온다고 했을 때,다음 숫자가 들어왔을 때 그보다 작은 숫자들 중 최대인 녀석을 찾고 거기에 +1 한 값과 DP에 써져있는 값을 비교해서 큰 녀석을 DP에 update 한다.
   • 이와 같은 풀이를 진행하면 C = 50, N = 500, 모든 수가 1~ 100000을 다 지나간다고 했을 때 대략 50 * 500 * 100000 정도의 시간복잡도가 될 거고 이는 25억이 되어 시간초과가 발생할 거라 생각했다.
2. update하면서 가장 큰 최댓값을 기억해두고 마지막에 이를 출력한다.
3. 해당 숫자를 맨 오른쪽 끝으로 하는 수열의 길이를 DP에 적어둔다.
4. 1번의 알고리즘에서 들어온 숫자를 DP에 update하는 알고리즘은 동일하지만 들어온 숫자들을 써두는 myV를 만들어서 비교할 때 1부터 들어오지 않은 모든 수를 비교하지 않고 들어왔던 수 중 작은 수들만 DP의 값을 비교하도록 만들었다.
   • 이렇게 하게되면 50 * 500 * 500보다 작은 시간복잡도를 가지고 1천만 정도 이내에 수행될 수 있을 거라 생각하였다

코드

//!2020.02.18
// TODO AS_LIS (Longest Increasing Sequence)
#include<cstdio>
#include<vector>
using namespace std;

const int MAX = 1000050;
vector <int> myV;
int DP[MAX];
int N, C;

int findMax(int number) {
    int maxRet = 0;
    for (int i = 0; i < myV.size(); i++) {
        int idx = myV[i];
        if (idx < number && maxRet < DP[idx]) maxRet = DP[idx];
    }
    return maxRet;
}

int main() {
    scanf("%d", &C);
    for (int c = 0; c < C; c++) {
        scanf("%d", &N);

        int result = -1;
        for (int n = 0; n < N; n++) {
            int num = 0;
            scanf("%d", &num);
            if (DP[num] == 0) myV.push_back(num);
            int tmpRet = findMax(num)+1;
            //printf("%d\n", tmpRet);
            if (DP[num] < tmpRet) DP[num] = tmpRet;
            if (result < tmpRet) result = tmpRet;
        }
        printf("%d\n", result);

        for (int i = 0; i < MAX; i++) DP[i] = 0;
    }
    return 0;
}