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 :]