package com.interview.dynamic;

/**
 * http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/
 */
public class LongestIncreasingSubsequence {

    public int longestSubsequenceWithActualSolution(int arr[]){
        
        int temp[] = new int[arr.length];
        int actualSolution[] = new int[arr.length];
        for(int i=0; i < arr.length; i++){
            temp[i] = 1;
            actualSolution[i] = i;
        }
        
        for(int i=1; i < arr.length; i++){
            for(int j=0; j < i; j++){
                if(arr[i] > arr[j]){
                    if(temp[j] + 1 > temp[i]){
                        temp[i] = temp[j] + 1;
                        //set the actualSolution to point to guy before me
                        actualSolution[i] = j;
                    }
                }
            }
        }
        int maxIndex = 0;
        for(int i=0; i < temp.length; i++){
            if(temp[i] > temp[maxIndex]){
                maxIndex = i;
            }
        }
        
        //lets print the actual solution
        int t = maxIndex;
        int newT = maxIndex;
        do{
            t = newT;
            System.out.print(arr[t] + " ");
            newT = actualSolution[t];
        }while(t != newT);
        System.out.println();
 
        return temp[maxIndex];
    }
    
    private int longestSubsequenceRecursive(int arr[], int pos, int lastNum){
        if(pos == arr.length){
            return 0;
        }
        int t1 = 0;
        if(arr[pos] > lastNum){
            t1 = 1 + longestSubsequenceRecursive(arr, pos+1, arr[pos]);
        }
        int t2 = longestSubsequenceRecursive(arr, pos+1, lastNum);
        return Math.max(t1, t2);
    }
    
    public int longestSubsequenceRecursive(int arr[]){
        int maxLen = 0;
        for(int i=0; i < arr.length-1; i++){
            int len = longestSubsequenceRecursive(arr,i+1,arr[i]);
            if(len > maxLen){
                maxLen = len;
            }
        }
        return maxLen + 1;
    }
    
    public static void main(String args[]){
        LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
        int arr[] = {23,10,22,5,33,8,9,21,50,41,60,80,99, 22,23,24,25,26,27};
        int result = lis.longestSubsequenceWithActualSolution(arr);
        int result1 = lis.longestSubsequenceRecursive(arr);
        System.out.println(result);
        System.out.println(result1);
    }
}

@@ -29,16 +29,563 @@
 c;%0A%0A/**%0A
+ * Date 05/02/2014%0A * @author tusroy%0A * %0A * Youtube link - https://youtu.be/CE2b_-XfVDk%0A * %0A * Find a subsequence in given array in which the subsequence's elements are %0A * in sorted order, lowest to highest, and in which the subsequence is as long as possible%0A * %0A * Solution : %0A * Dynamic Programming is used to solve this question. DP equation is %0A * if(arr%5Bi%5D %3E arr%5Bj%5D) %7B T%5Bi%5D = max(T%5Bi%5D, T%5Bj%5D + 1 %7D%0A * %0A * Time complexity is O(n%5E2).%0A * Space complexity is O(n)%0A * %0A * Reference %0A * http://en.wikipedia.org/wiki/Longest_increasing_subsequence%0A
  * http:
@@ -800,20 +800,17 @@
     int 
-temp
+T
 %5B%5D = new
@@ -930,28 +930,25 @@
             
-temp
+T
 %5Bi%5D = 1;%0A   
@@ -1139,20 +1139,17 @@
      if(
-temp
+T
 %5Bj%5D + 1 
@@ -1150,20 +1150,17 @@
 %5D + 1 %3E 
-temp
+T
 %5Bi%5D)%7B%0A  
@@ -1185,22 +1185,16 @@
     
-temp
+T
 %5Bi%5D = 
-temp
+T
 %5Bj%5D 
@@ -1376,32 +1376,86 @@
     %7D%0A        %7D%0A
+        %0A        //find the index of max number in T %0A
         int maxI
@@ -1489,20 +1489,17 @@
 =0; i %3C 
-temp
+T
 .length;
@@ -1524,22 +1524,16 @@
  if(
-temp
+T
 %5Bi%5D %3E 
-temp
+T
 %5Bmax
@@ -1894,12 +1894,9 @@
 urn 
-temp
+T
 %5Bmax
@@ -1910,24 +1910,337 @@
 %0A    %7D%0A    %0A
+    public int longestSubsequenceRecursive(int arr%5B%5D)%7B%0A        int maxLen = 0;%0A        for(int i=0; i %3C arr.length-1; i++)%7B%0A            int len = longestSubsequenceRecursive(arr,i+1,arr%5Bi%5D);%0A            if(len %3E maxLen)%7B%0A                maxLen = len;%0A            %7D%0A        %7D%0A        return maxLen + 1;%0A    %7D%0A    %0A
     private 
@@ -2617,321 +2617,8 @@
    %0A
-    public int longestSubsequenceRecursive(int arr%5B%5D)%7B%0A        int maxLen = 0;%0A        for(int i=0; i %3C arr.length-1; i++)%7B%0A            int len = longestSubsequenceRecursive(arr,i+1,arr%5Bi%5D);%0A            if(len %3E maxLen)%7B%0A                maxLen = len;%0A            %7D%0A        %7D%0A        return maxLen + 1;%0A    %7D%0A    %0A
     

Update video link in LIS