300. 最长递增子序列+输出序列

class Solution {
    public List<Integer> getLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        
        // 【新增】用来记录前驱节点的索引，-1 表示没有前面没有接人
        int[] prev = new int[n]; 
        for(int k = 0 ; k < n ; k++) {
            dp[k] = 1;
            prev[k] = -1; // 默认都没有老大哥
        }
        
        int maxLen = 1;
        int maxIndex = 0; // 【新增】记录最长子序列是以哪个索引结尾的
        
        for(int i = 1 ; i < n ; i++){
            int maxLength = 0;
            int bestJ = -1; // 【新增】记录到底接在哪个 j 后面最划算
            
            for(int j = i - 1; j >= 0 ; j--){
                // 注意这里：不能单纯用 Math.max 了，因为我们要知道具体的 j 是谁
                if(nums[j] < nums[i] && dp[j] > maxLength){ 
                    maxLength = dp[j];
                    bestJ = j; // 记住最牛老大哥的名字（索引）
                }
            }
            dp[i] = maxLength + 1;
            prev[i] = bestJ; // 正式把老大哥登记在册
            
            // 顺手更新全局最大值，并记下这个巅峰是属于谁的（maxIndex）
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIndex = i;
            }
        }
        
        // 【新增阶段】顺藤摸瓜，收集结果
        List<Integer> res = new ArrayList<>();
        int curr = maxIndex; // 从巅峰位置开始往回回溯
        
        while (curr != -1) {
            res.add(nums[curr]); // 把当前数字收进袋子
            curr = prev[curr];   // 顺着线索找上一个老大哥
        }
        
        // 因为我们是倒着往回找的，所以收集到的序列是反的，翻转过来！
        Collections.reverse(res); 
        
        return res;
    }
}