The longest increasing subsequence problem is a dynamic programming problem that calculates the length of a non-contiguous subsequence from a given sequence. For example, given the sequence:
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
A subsequence is 0,4,2,1,5. An increasing subsequence is 0,4,10,14,15. The question is to find the length of the longest increasing subsequence, which has size 6 (0, 2, 6, 9, 13, 15). Note that the sequence might not be unique, but you need to find the length of the longest subsequence.
public class LIS { public static void main(String[] args){ int[] num = {2,6,4,5}; int[] pos = {2, 4, 3, 5, 1, 7, 6, 9, 8}; printLIS(num); } public static void printLIS(int[] num){ String[] paths = new String[num.length]; int[] sizes = new int[num.length]; for(int i = 0 ; i < num.length ; i++){ sizes[i] = 1; paths[i] = sizes[i] + " "; } int maxlength = 1; for(int i =1 ; i < num.length ; i++){ for(int j = 0 ; j < i; j++){ if(num[i] > num[j] && sizes[i] < sizes[j] +1){//in LIS so we add one sizes[i] = sizes[j] +1; paths[i] = paths[j] + num[i] + " "; if(maxlength < sizes[i]){ maxlength = sizes[i]; } } } } for(int i =1; i < num.length ; i++){ if(sizes[i] == maxlength) System.out.println("LIS: " + paths[i]); } } }