Dynamic Programming : Largest Increasing Sub Sequence

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