Longest Increasing sequence

LIS.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int a[] = {4, 3, 1 ,2, 8, 3, 4};
// int a[] = {1, 6, 2 ,3, 4, 5, 7};
// int a[] =  {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
// int a[] =  {5,4,6,3,7};

int N = sizeof(a)/sizeof(a[0]);

int dp[50] = {1};

int main(){
    /* 
        We should search for longest increasing subsequence(LIS) with K elements first,
        then it can be extended to (K + 1)th element. So we build a table with lengths 
        of longest sequences for each index till K. When we have the (K + 1)th element,
        we should try to search for an element in the previous K elements which can 
        be the predecessor to this element.

        From the data set : {4, 3, 1 ,2, 8, 3, 4}

        E [L] - Element, and length of longest increasing subsequence. 
        4 [1] - It is the only element so far, so we have the length of LIS as 1
        3 [1] - If we observe, the previous number is 4 which is greater than the current.
                      So we cannot reach 3 from 4. so the length is still 1.
        1 [1] - Same in this case.. 3 is larger than 1. so the length of LIS is still 1.
        2 [2] - If we scan the numbers before 2, we find 1, a number which can be a 
              predecessor to 2. So we increment the length from 1 to 2 (dp[i] = dp[j] + 1).
        8 [3] - We see that, we can reach 8 from 2. So, we increase the length from 2 to 3.
        3 [3] - Again, we can reach 3 from 2. So, we pick 2 as the predecessor.
        4 [4] - We can reach 4 from 3. So we incremenet the length once again.
    */
    int ans = 1;
    for(int i=1;i<N;i++){
        dp[i] = 1;
        for(int j = i - 1 ; j >= 0; j--){
            if(a[j] < a[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
    }

    cout << ans << endl;
    return 0;
}