1965 상자넣기 (오답, LIS 접근 필요)

#include <stdio.h>
#include <vector>
 
using namespace std;
 
vector<int> vec;
int adj[100][100] = { 0 };
const int INF = 978654312;
 
int main() {
    int n, num;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        vec.push_back(num);
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            adj[i][j] = (i == j) ? 0 : INF;
        }
    }
 
    for (int i = 0; i < n - 1; i++) {
        int from = vec[i];
        int to = vec[i + 1];
 
        adj[from][to] = 1;
    }
 
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (adj[i][j] > adj[i][k] + adj[k][j])
                    adj[i][j] = adj[i][k] + adj[k][j];
            }
        }
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (adj[i][j] == INF)
                adj[i][j] = 0;            
        }
    }
    int maxPath = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (maxPath < adj[i][j])
                maxPath = adj[i][j];
        }
    }
 
    printf("%d", maxPath);
}