Path reconstructions for LIS

[Sung-Pil_Paek]

class LIS {

  public int findLISLength(int[] nums) {
    int[] dp = new int[nums.length];
    int[] prev = new int[nums.length];
    java.util.Arrays.fill(dp, 1);
    prev[0] = -1;

    int max = 1;
    int end = 0;
    for (int i = 1; i < nums.length; i++) {
      prev[i] = -1;
      
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          if (dp[i] < 1 + dp[j]) {
            dp[i] = 1 + dp[j];
            prev[i] = j;
          }
        }

        if (max < dp[i]) {
          max = dp[i];
          end = i;
        }
      }
    }

    java.util.List<Integer> path = new java.util.LinkedList<>();
    while (end != -1) {
      path.add(0, nums[end]);
      end = prev[end];
    }

    System.out.println(path);

    return dp[nums.length - 1];
  }

  public static void main(String[] args) {
    LIS lis = new LIS();
    int[] nums = {4,2,3,6,10,1,12};
    System.out.println(lis.findLISLength(nums));
    nums = new int[]{-4,10,3,7,15};
    System.out.println(lis.findLISLength(nums));
  }
}

Same approach applies to finding an actual path for finding minimum jumps in Fibonnaci chapter :]