Some Dynamic Programming from scratch!
The programming world is so rude, whenever they want to test you, they ask a problem and before you begin to solve, most of the times you have to tackle dynamic programming trick to get it done. I have been coding for decent times now. Only place where I have to use DP is contest. I wish, I get a job where I practically have to implement it as well..
Never the less, starting from scratch taking one problem today
Question: Length of Largest Increasing Sub-sequence.
Defining array : A[] = {a1,a2,a3....an};
Answer = Length of largest increasing sub-sequence L
So, I define another array L[] = {empty of size N} which will numbers such that
L[r] = Length of largest sub-sequence starting at index r
What we know... L[N] = 1....yaaaay!!!!! --> get this setup in my array!
going bottom up... and building my array now!!
L[N-1] = {1 if A[N-1] > A[N] else 2 }
L[N-2] = {1 if A[N-2] > A[N-1] else (L[N-1]+1) }
so L[r] = {1 if A[r] > A[r+1] ; else (L[r+1]+1) with L[N]=1}
loop r from N to 1 and there we go
(please see, in notations above, I have used 1 as first index not zero)
Crux Code
public static void largestIncSeq(int[] A){
int N = A.length;
int n = N-1; //human readable indexing!
int[] L = new int[N];
L[n] = 1; //sure answer
for (int r=n-1; r>0; r--){
if (A[r+1] < A[r])
L[r] = 1;
else
L[r] = L[r+1]+1;
}
}
Complete code that demonstrate the same:
public class LargestSubSeqLen{
public static void main(String[] a){
int[] input = {1,4,5,4,5,6,7,8,3,2,1};
System.out.print("Input Array = ");
for (int i =0 ; i< input.length; i++){
System.out.print(input[i]);
if (i!=input.length-1){
System.out.print(",");
}
}
System.out.println();
int output = largestIncSeq(input);
System.out.println("Largest Sequence Size : "+output);
}
public static int largestIncSeq(int[] A){
int N = A.length;
int n = N-1; //human readable indexing!
int[] L = new int[N];
L[n] = 1; //sure answer
System.out.println("Setting L["+n+"] as 1");
for (int r=n-1; r>=0; r--){
if (A[r+1] < A[r])
L[r] = 1;
else
L[r] = L[r+1]+1;
System.out.println("Setting L["+r+"] as "+L[r]);
}
int max = 0;
int maxInitIndex = 0;
for (int r=0; r<N; r++){
if (L[r]>max) {
max = L[r];
maxInitIndex = r;
}
}
System.out.print("Largest Increasing Sequence:");
for (int i=maxInitIndex; i<max+maxInitIndex; i++){
System.out.print(A[i]);
if (i!=max+maxInitIndex-1)
System.out.print(",");
}
System.out.println();
return max;
}
}
Sample I/O:
zeek@zeek ~/code/java/dynamicProb $ javac LargestSubSeqLen.java
zeek@zeek ~/code/java/dynamicProb $ java LargestSubSeqLen
Input Array = 1,4,5,4,5,6,7,8,3,2,1
Setting L[10] as 1
Setting L[9] as 1
Setting L[8] as 1
Setting L[7] as 1
Setting L[6] as 2
Setting L[5] as 3
Setting L[4] as 4
Setting L[3] as 5
Setting L[2] as 1
Setting L[1] as 2
Setting L[0] as 3
Largest Increasing Sequence:4,5,6,7,8
Largest Sequence Size : 5
