질문 내용

안녕하세요. 교재 참고하여 LIS 문제 풀던 중
(https://algospot.com/judge/problem/read/LIS)
페이지 234의 코드 8.12를 JAVA로 변환해서 제출해보았는데
계속 오답이 나서 질문 올리게되었습니다.
앞의 코드 8.11을 JAVA로 변환했을때는 정답이어서 더 혼동되네요.

코드는 아래와 같은데 교재의 코드를 그대로 포팅했고
일단 제가 보기에는 로직 상에도 문제가 없어서 문제점을 찾지 못 하고 있습니다.

혹시 잘못된 부분이 있거나
오답이 되는 테스트케이스라도 알려주셨으면 감사합니다.

코드

import java.util.Scanner;

public class Main {
    static int[] cache = new int[501];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        while(tc-->0) {
            // N <= 500
            int n = sc.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<arr.length;i++) {
                // 각 정수는 1 이상 100,000 이하
                arr[i] = sc.nextInt();
            }
            int max = getLongest(arr, -1)-1;
            System.out.println(max);
            // 캐시 초기화를 잊지 않습니다.
            // 캐시 초기화를 잊지 않습니다.
            // 캐시 초기화를 잊지 않습니다.
            cache = new int[501];
        }
        sc.close();
    }
    
    static int getLongest(int[] arr, int i) {
        int result = cache[i+1];
        if(result != 0) {
            return result;
        }
        
        result = 1;
        for(int j=i+1;j<arr.length;j++) {
            if(i==-1 || arr[j] > arr[i]) {
                cache[i+1] = result = Math.max(result, getLongest(arr, j) + 1);
            }
        }
        return result;
    }
}