Longest Increasing Sub-sequence(Dynamic Programming)

Problem Statement:

Suppose you have a given a integer sequence a[1..n]. You have to find the longest increasing sub sequence i.e. the sub sequence should be in increasing order with largest length possible in the given sequence.

Let suppose you have following sub sequence:

Longest increasing sub sequence is : 0, 2, 3, 4, 9, 12, 15.

is there any other longest or same length sub sequence is there?

Yes : 0, 2, 3, 4, 8, 12, 15

So both have the same length 7. Make sure no other sub sequence should have length greater than 7.

Just try ? If you able to find please add comment in the post we will discuss that.

So our main problem is how to solve this problem programatically? We will again discuss the various approach and then the one with Dynamic programming.

Solution Approach:

Brute Force Approach:

In brute force approach we will calculate all the possible sub sequence and then check for the longest sub sequence. So for calculating all the sub sequence is tedious task and take O(2n) complexity.
If three elements are there like
0
2
7
0, 2
0, 7
2, 7
0, 2, 7

So we have all the possible combination and longest is 0, 2, 7. So it is not a optimum solution.
We will not go with the solution.

Dynamic Approach:

We know that to solve any problem with dynamic approach it must have two attributes:

Optimal Substructure:
The solution is known has optimal sub structure if optimal solution can be construct from the optimal solutions of sub problem.

Can we do that in this situation ?
In above scenario what if i know that the longest sub sequence for all the indexes upto 5. Can i use that for calculating the sub sequence for  index  6 ?

Yes the sub sequence of index 6 can be

longSubsequence (6) = {
                                           max(longSubsequnce(j) + 1) where j:1...5 and  if a[6] > a[j],
                                           1        if no j found such that all a[j] is greater than a[6].
                                     }
So longest sub sequence of 6 can be calculated if we know the longest sub sequence of 5. So solution has optimum Sub structure.

Overlapping Subproblem(Recursion):
For Solving the maxSubsequence of 6 we need to solve the longestsubsequence of 5, 4, 3, 2 and1. So the problem has recursion possibly.

Solution:
We will start with the longest sub sequence for index 0 and go upto array length.
ls[0] = 1 //Only one element can be in sub sequence for length 1 array.

ls[1] = 2 // (0, 2) as a[1] is greater than a[0] So we can add it.

ls[2] = 1+ max(ls[0],ls[1]) as 7 is greater than both 0 and 2.
ls[2] = 1+max(1, 2)
         = 3

ls[3] = 1+max(ls[0], ls[1]) as a[3] < a[2] So we cannot consider that in the formula.
ls[3] = 1+max(1, 2)
         = 3

ls[4] = 1+max(ls[0], ls[1], ls[3]) as a[4] is less than a[2] so we cannot consider this
ls[4] = 1+max(1, 2, 3)
        = 4

ls[5] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4]) as 9 is greater than all the previous element.
        = 1+ max(1, 2, 3, 3, 4)
        = 5

ls[6] =  1+max(ls[0], ls[1], ls[2], ls[3], ls[4]) as 8 is less than 9 the previous element.
        =  1+ max(1, 2, 3, 3, 4)
        = 5

ls[7] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4], ls[5], ls[6]) as 12 is greater than all the previous element.
        = 1+ max(1, 2, 3, 3, 4, 5, 5)
       = 6 (0, 2, 3, 4, 9, 12) or (0, 2, 3, 4, 8, 12)
ls[8] = 1 as a[8] is less than all the previous element.

ls[9] = 1+max(ls[0], ls[1], ls[2], ls[3], ls[4], ls[5], ls[6], ls[7], ls[8]) as 15 is greater than all the previous element.
         = 1+ max(1, 2, 3, 3, 4, 5, 5, 6, 1)
         = 7 (0, 2, 3, 4, 9, 12, 15) or (0, 2, 3, 4, 8, 12, 15)

So we have solution with the above approach. Can we phrase the solution in one formula:

ls[i] = 1+max(ls[j]) where j:0...i if a[i] >  a[j]
           or
           1 if no such j found.

So I have implemented the solution using C. Following is the solution:

I am using a heap to store longest sub sequence for each index. Like for zero index the longest sub sequence only have one length and first element. So other we are calculating based on that above formula.

Following is heap structure:

//Use as a heap for store the longest sequence for index

typedef struct lsIncreasingSequence_struct{

    int longesubSequence[10];

    int longesubequenceLength;

}lsIncreasingSequence;

Calculating the longest sub sequence following is the code:

//return the longest sequence

lsIncreasingSequence longIncSubsequence(int sequence[], int seqL){

    lsIncreasingSequence lsubsequences[seqL+1]; //Store the longest sequence for each index

    int finalsubsequenceLength = 0;      //Store the longest sequence length

    int finalSubSequenceIndex = -1;       //Store the longest sequence index

    lsubsequences[0].longesubSequence[0] = sequence[0]; //First sequence have only first element

    lsubsequences[0].longesubequenceLength = 1;  //First sequence have only first element so count is 1

    

    //Loop Start from second element and count longest sequence for each index

    for (int i=1; i<seqL; i++) {

        //Loop check for all the possible sub sequence and check if length is largest

        for(int j=0; j <i ; j++){

            if(sequence[i] > sequence[j]){

                finalsubsequenceLength = lsubsequences[j].longesubequenceLength + 1;

                if(finalsubsequenceLength > lsubsequences[i].longesubequenceLength){

                    lsubsequences[i].longesubequenceLength = finalsubsequenceLength;

                    finalSubSequenceIndex  = j; //Store the largest increasing sub sequence for index i

                }

            }

        }

        

        //loop copy all the elements of longest sub sequence of i to index i of heap

        if(finalSubSequenceIndex != -1){

            int k = 0;

            for(; k < lsubsequences[i].longesubequenceLength-1; k++){

                lsubsequences[i].longesubSequence[k] = lsubsequences[finalSubSequenceIndex].longesubSequence[k];

            }

            lsubsequences[i].longesubSequence[k] = sequence[i];

        }

        finalSubSequenceIndex = -1;

    }

    //loop calculate longest increasing sub sequence from all the indexs in a heap

    finalsubsequenceLength = 0;

    for (int k=0; k<seqL; k++) {

        if(lsubsequences[k].longesubequenceLength > finalsubsequenceLength){

            finalsubsequenceLength = lsubsequences[k].longesubequenceLength;

            finalSubSequenceIndex = k;

        }

    }

    //return the longest sub sequence heap element

    return lsubsequences[finalSubSequenceIndex];

}

So the above method return the longest sub sequence.
You can download the running code from the link.
Please provide your suggestion.

Maximum Sub-Sequence Sum in Array (Dynamic Programming)

Problem Statement:

Suppose you have a given a integer array a[1..n]. You have to find the maximum sub sequence sum i.e. the sum of the numbers should be greater than any other sequence.

Suppose you have given an following array:

-2

-3

4

-1

-2

1

5

-3

You need to find the maximum subsequence?

We as normal human tendency always try to discard the negative number in sequence. So most of us will go with the solution 1,5 = 6 is sum of maximum sub sequence.

But that solution is wrong as the maximum sub sequence has sum 7.If you already chosen the best solution than it is great :).

Let try to search once again for the best solution without seeing below ;).

So Solution is 4, -1, -2 , 1,  5. Sum is 7.

So now we have to implement this solution by programming. We will discuss the various approach and then will try our solution with dynamic programming.

Solution Approach:

Brute Force Approach:
In brute force approach we will solve the problem in O(n) Complexity. In this approach we will iterate over each element and start doing sum until the length of array and after adding each element check sum if it is greater than max sum then replace the max sum with new value.

Note: This algorithm is implemented in this way that we always focus that sum cannot be less than zero.

Following is example

Max sum = 0;
sum = 0;

i = 0(-2)
sum = sum + (-2);
sum = -2.
So sum is less than zero so discard this sum and initialize the sum with zero.
i=1(-3)
sum = -3;
So sum is less than zero so discard this sum and initialize the sum with zero.
i=2(4)
sum = 4; 

So sum is greater than zero and max sum. So replace the max sum with sum and keep the sum.

i=3(-1)
sum = 3

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.

i=4 (-2)

sum = 1

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
i=5(1)

sum = 2

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
i=6(5)
sum = 7
So sum is greater than zero and max sum(4). So replace the max sum with sum and keep the sum.
i=7(-3)

sum = 4

So sum is greater than zero but not greater than max sum. So keep the sum but not replace with max sum.
So in the end we have 7 in max sum this is our solution. We solve the problem in linear time.
The solution we provide here is according to well known Kadane's algorithm.

Dynamic Approach:

Dynamic programming solution is similar to Kadane's algorithm. We already know to solve any problem with dynamic programming it must have to attributes.

Optimal Substructure: We can solve the problem of length n by solving the lower problem. If we know the solution for i then for i+1 following will be the solution:
max(solution[i]+a[i+1],  a[i+1]);
solution[i] denotes maximum sub sequence sum for ith element.

But in this case storing solution[i] is an over head. We can simple solve the problem in linear time with time complexity O(N) and space complexity with O(1). But our topic is dynamic programming we are providing solution through dynamic approach.

Solution
Running Time : O(N)
Space Complexity: O(N)

Solution:

int calculateMaximumSubSequence(int array[], int size){

    int max[size]; // Store max sub sequence at each index. We do not need this as Kadan's algo but for dynamic approch we are using that

    memset(max, 0, size);

    int maximumSubsequence = 0; // Store max sub sequence for array

    max[0] = array[0];

    for(int i = 1; i < size;i++){

        // Check if previous max sib sequence is greater than zero. If it is negative then our condition solution[i]+a[i+1] is always less than a[i+1]

        if(max[i - 1] > 0){

            max[i] = max[i-1]+array[i];

        }else{

            max[i] = array[i];

        }

        // Store the max sub sequence for array

        if(maximumSubsequence < max[i]){

            maximumSubsequence = max[i];

        }

    }

    return maximumSubsequence;

}

You can download full source code from the link:
Please provide your input and suggestion on the tutorial.

Cut a Road with Maximum Profit (Dynamic Programming)

Problem Statement:

Let suppose you have a rod of some length x inches and given a array of prices that contain prices of all size less than x. You need to calculate the maximum price value by cutting the road and selling the pieces.

Let understand with example. Suppose you have a rod of length 8 inch and the value of differnet pieces is given below:

Length	1	2	3	4	5	6	7	8
Price	1	5	8	9	10	17	17	20

   

So If we do not cut the road then we can sell it with price 20 rs. is there any better solution so that price can be increase ?

If we cut it in equal piece (4, 4) then we have price 18. 9+9.

So from the above table if we cut it in 6,2 then we have maximum price 22. So it is our solution.

Solution Approach:

Brute-Force Approach:

Brute force approach is simple you need to calculate each pair cost and select the maximum one. It is simple but take long time to execution. Running time for the brute force approach is exponential.

Explanation of the approach:

Let suppose maximum price for length L is M[L]. To calculate M[L] we will calculate the maximum price M[X] for all X such that X < L.

So start with M[1] = 1
M[2] = 5 because if go for p[1] + p[1] =  2 which is less than 5. So here we are doing max of all the cases.
M[3] = max(p[1]+p[1]+p[1], p[2]+p[1], p[3])
 = max(1+1+1, 5+1, 8)
 = max(3, 6, 8)
 = 8
M[4] = max(p[1]+p[1]+p[1]+p[1], p[2]+p[2], p[3]+p[1],  p[2]+p[1]+p[1] , p[4])
        = max(4, 5+5, 8+1, 5+1+1,  9)
       = max(4, 10, 9, 7, 9)
       = 10
M[5] = max (p[4]+p[1],  p[3]+p[2] ,  p[3]+p[1]+p[1],  p[2]+p[2]+p[1],  p[2]+p[1]+p[1]+p[1],  p[1] +p[1] +p[1] +p[1] +p[1] , p[5])
       = max(11, 13,  10,11,  8, 5, 10)
       =13 (3, 2) is the best for cut a road of length 5.

Do we need to examine all of this it is also very tedious task. So is there any better solution ?

Adding Existing Max Price To Solution:

When we are calculating M[4] maximum price for length 4 we already know the price of M[3] , M[2] M[1] but we are not using that in above approach :(.

So when we are calculating M[4] we start with  adding price for length 1 So length 3 has left. Then there are various options for length 3 we tried in above example like p[1] + p[1]+p[1] , p[2] + p[1] , p[3]. But we forget we already know the M[3] for the length 3 and no options will be better than M[3]. So why not use that :).

Explanation of the approach:

M[0] = 0

M[1] = 1

M[2] = max (p[1] + M[1] , p[2]+M[0])

M[3] = max (p[1] + M[2], p[2]+M[1],p[3]+M[0])

M[4] = max(p[1]+M[3], p[2]+M[2], p[3]+M[1], P[4]+M[0])

and So on.

It is simple approach and easier to calculate.

So in mathematical term we can write this as:
M[n] = max(p[i]+m[n-i-1])
             0<=i<n

Recursive Approach:

It is similar to the approach we discussed in the coin-change problem of dynamic programming.
We will apply the above formula to calculate the maximum price. So for M[8] it will calculate the M[7], M[6], M[5] and So on.
But there is one problem in recursion a same M[i] will be calculate again and again. Suppose you are calculating M[4] then following is recursion tree:

So in the above tree you can see M[2] is calculated 2 times. For the larger problem the same max price is calculated multiple time.

We can use dynamic programming for the better run time.

Dynamic Programming  Approach:

We will save the previous M[i] value for calculating the M[i]. In this case we will start from 0 to calculate maximum benefit and then reach to M[8] as explained above in Adding Existing Max Price To Solution section.

We forgot one thing to solve a problem with dynamic programming it must have two attributes:

1) Optimal substructure : Yes we are solving it by first solving the small solution like M[0] , M[1]
2) Overlapping Subproblem: We have seen in above case a same M[2] is calculated multiple time.

So we can apply dynamic programming here and following is solution with dynamic programming:

Following is solution with C programming:

int cutroad(int price[], int rodLength){

    int maxBenefit[rodLength + 1]; // Store the max benefit for all the length 0...8 in our case

    int solution[rodLength];     // use for calculating all the possible result for each length 1...8

    int finalSolution = -1;

    memset(maxBenefit, 0, rodLength);

    //Start from the length 1 to 8. This loop used for calculate the maxbenefit for the lenght 1 to 8.

    for (int i = 1;  i < rodLength +1; i++) {

        memset(solution, -1, rodLength);

        //Loop used fo calculate possible solution for particular lenght like for 2.M[2] = max (p[1] + M[1] , p[2]+M[0])

        for (int j=0; j < i; j++) {

            solution[j] = price[j]+maxBenefit[i-j-1];

        }

        // Calculate max benefit from all the possible solution.

        for (int k=0; k< i; k++) {

            if(solution[k] >= 0){

                if (finalSolution == -1 || finalSolution < solution[k]){

                    finalSolution = solution[k];

                }

            }

        }

        maxBenefit[i] = finalSolution;

    }

    return maxBenefit[rodLength];

}

You can download full source code from the link.

Minmum Coin Change Problem

Problem Statement:

Every country has different type of bank notes and face value of each banknote is different.  Like in india we have banknote of 1, 2, 5, 10, 20 .... and so on :). So in today problem we only focus on lower bank note value not bigger.

Problem is if you have 1, 2, 5, 10 bank notes and you want to make change for the 17. There are multiple solution for that:

{10,5,2}

{5,5,5,2}

{10,5,1,1}

So we come across number of solution. Our aim is develop an algorithm with minimum number of coins So in our case we need a optimal solution  {10,5,2}.

We can write the problem in following manner:

Given a set of integer value Let {r1, r2 , r3... , rn } where r1 =1  and rj < rj+1 for 1<= j <= n-1, and a positive value W(17 from above). find a non negative set of integers which minimize.

n

∑xj

j=1

such that

n 

∑rjxj = W

j=1

Solution:

We will follow the approach of calculating change require for the all the x where x < w. 

Let suppose c[p] is minimum change (rupees change) require for the p rupees. For calculating the c[p] we need to calculate c[x] where x < p.

So what will be the c[p] ? 

c[p] = min : ri <= p { c[p - ri ] } + 1 if p > 0

            i                           0  if p = 0

Let understand the solution if we need a change for 7 rupees and we have coin for 1, 2 , 5.

We need to calculate c[7] with r = {1,  2,  5}.

First Calculate c[0] = 0  as p = 0

c[1] = min {c[1-1] } + 1  // We cannot consider 2 and 5 as the ri <= p condition does not met 2  > 1 and 5 > 1.

C[1] = min {0} + 1 = 1

C[2] = min {c[2-1],  c[2-2] }  + 1

c[2] = min {1 , 0} + 1

c[2] = 1 So we can calculate c[2] by just one coin 2

c[3] = min {c[3-1],  c[3-2] }  + 1

       = min {c[2] , c[1] } + 1

       = min {1 , 1} + 1

       = 1+1 = 2 // So we need two bank note for change of 3.

c[4] = min {c[4-1],  c[4-2] }  + 1

       = min {c[3] , c[2]} + 1

      = min {2, 1} + 1

     = 1+1 = 2 // right we need only two coin (2,2)

c[5] = min {c[5-1],  c[5-2] , c[5-5] }  + 1

       = min {c[4] , c[3] , c[0] } + 1

      = min {2 , 2 , 0} + 1

      = 1 // right now we have bank note 5 as ri <= p condition met where ri is bank note which is equal to 5 and p is also 5 we need change of 5.

c[6] = min {c[6-1],  c[6-2] , c[6-5] }  + 1

       = min {c[5] , c[4] , c[1]} + 1

      = min {1, 2, 1} + 1

      = 1 + 1 =  2 // (5, 1) or (1 , 5)

c[7] = min {c[7-1],  c[7-2] , c[7-5] }  + 1

       = min {c[6] , c[5] , c[2]]} + 1

       = min {2 , 1 , 1} + 1

      = 2 // (5,2 ) or (2, 5)

So our solution approach is right. 

How it works ? 

Just forget the problem and suppose you want to reach at value S with minimum addition of the values from the set {c1 ,  c2 ,  c3 , --- cn}. What approach you will take.

Greedy Approach:

Take the larger value from set try to add it two times or three times and check if it is larger than S. Then try to add lower value and so on. is it work every time ?
Try on this Sum = 30
{1, 15, 25}

No it will not work for the above case :).

Recursive Approach:

Let suppose you know the minimum number from the set require to make the sum S and it is following:

{C1, C2,  C2, C3}

We know one fact here if i do S-C3 the {C1, C2, C2} is the minimum numbers require for the sum C1+C2+C2.

Confusing ?

Let you have to make the sum 17 with the value {1, 3, 5}

then value is {1, 1, 5, 5, 5}

I am picking up the last value 5 and subtract it from 17. 17-5 = 12

and the remaining number is {1, 1, 5 , 5}.

So it is minimum number require for 12.

Now if i pick the last one again then {1, 1, 5} is minimum for 7.

So what i am doing here i am just subtracting the given value(17) from the set of to the number {1, 3, 5}.

If sum is 4 then we have {1, 3}

4-3 = 1 so we require only one value from the set that is {1} and it is true.

So can we apply this solution to our problem ?

Let suppose you have to make the coin change for 17 with the coin {1, 3, 5}.

Try to calculate C[17 - 5] , C[17 - 3] , C[17 -1] ? Which one is minimum add 1 into that. It is your solution :). So for this you need to calculate c[12], c[14] , c[16]. In this manner we need to calculate 

c[7],c[11], c[15] and so on.

Running Time:
Recursive approach will provide you the right solution but it will take longer time to execute. Because it will re compute the solution again again for the same number. Like for c[12] it will calculated three time one for c[17 - 5], c[15-3], c[13-1].

Can we improve that? yes the approach is dynamic programming.

Dynamic Approach:

We can solve any problem with dynamic programming if problem solution has following two attributes:

1) optimal substructure : If optimal solution is constructed from the optimal solution of subproblem then the solution has optimal sub structure.

2) overlapping subproblem :  If problem can be broken into sub problem which are used several times.

So both the attributes can be applied on our problem so we can solve our problem by dynamic programming.

So we Follow the same solution as explain above in Solution section.
Let suppose you have to calculate the minimum coins require for rupees j. Then you need to calculate minimum coin for all the value less than j(Optimal substructure).

Running Time:
We need to calculate minimum coin change for all the value less than j. So one loop is require for iteration to 1...j. In each value we need to check for the minimum value by iteration over all the coin value. So nested loop is require for the solution.

Complexity will be O(jl).
Where j is value for which minimum coin change need to be calculate.
l is length of the coin set.  


Code:

int findMinimumCoinChange(int rs, const int coinSetPtr [], size_t coinSetLength){

    int minCoinValues[rs+1];

    int finalSolutiuon = 0;

    memset(minCoinValues, -1, sizeof(minCoinValues));

    minCoinValues[0] = 0;

    //Calculating the solution from 1 to given rs.

    for(int i = 1; i <= rs ; i++){

        int solution[coinSetLength];

        memset(solution, -1, sizeof(solution));

        // All possible solution for the value i

        for (int j=0; j < coinSetLength; j++) {

            if(coinSetPtr [j] <= i){

                solution[j] = minCoinValues[i - coinSetPtr[j]] + 1;

            }

        }

        

        finalSolutiuon = -1;

        // Minimum Possible solution for the value i

        for(int k=0;k < coinSetLength;k++){

            if(solution[k] > 0 ){

                if(minCoinValues[i] == -1 || solution[k] < minCoinValues[i]){

                    minCoinValues[i] = solution[k];

                }

            }

        }

        

        

    }

    return minCoinValues[rs];

}

You can download the full source code from the link

Now we are done with the coin change problem :).