longest increasing subsequence

import java.util.*;

public class Temp{
public static void main(String args[]){

StringBuilder sb=new StringBuilder();

int arr[]={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int dp[]=new int[arr.length];
int print[]=new int[arr.length];

dp[0]=1;

for(int i=1;i<arr.length;i++){
dp[i]=0;
print[i]=i;
//int max;
int temp=i;
for(int j=0;j<i;j++){
if(arr[i]>arr[j]){
dp[i]=(dp[i]>dp[j]) ? dp[i] : dp[j];
temp=(dp[i]>dp[j]) ? temp : j;
}
print[i]=temp;
}
dp[i]+=1;

}

for(int i=0;i<arr.length;i++){
System.out.print(dp[i]);
}

  System.out.println("\n");

System.out.print("print[i]");
for(int i=0;i<print.length;i++){
System.out.print(+print[i]);
}

System.out.println("\n");
// print longest common subsequesce...

int index=0;
int max=0;
for(int i=0;i<dp.length;i++){
if(max<dp[i]){
max=dp[i];
index=i;
}
}

int count=dp[index];
System.out.println("count = "+count);
System.out.println("index = "+index);

while(count>0){
sb.insert(0,arr[index]+" ");

index=print[index];

count--;
}

System.out.println(sb);


}
}

Longest common subsequesce

import java.util.*;

public class Temp{
public static void main(String args[]){

StringBuilder sb=new StringBuilder();
String str1="AGGTAB";
String str2="GXTXAYB";
int c[][]=new int[str1.length()+1][str2.length()+1];

for(int i=0;i<=str2.length();i++){
c[0][i]=0;
}

for(int j=0;j<=str1.length();j++){
c[j][0]=0;
}

for(int i=1;i<=str1.length();i++){
for(int j=1;j<=str2.length();j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
c[i][j]=1+c[i-1][j-1];
}
else{
c[i][j]=(c[i][j-1]>=c[i-1][j])?c[i][j-1]:c[i-1][j];
}
}
}


System.out.println(c[str1.length()][str2.length()]+"\n");

for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
System.out.print(c[i][j]);
}
System.out.println();
}


// print LCS.....

int i=str1.length();
int j=str2.length();

while(i>0 && j>0){
if(str1.charAt(i-1)==str2.charAt(j-1)){
sb.append(str1.charAt(i-1)+"");
i--;
j--;
}
else{
if(c[i][j-1]>=c[i-1][j]){
j--;
}
else{
i--;
}

}
System.out.println(i + " "+ j +"\n"  );

}

System.out.println(sb.reverse());


}
}