Longest Increasing Sub-sequence.

/*
    Guess
    =====
    If including element i forms maximum length increasing sequence.
    
    Sub-problem
    ===========
    Prefix of input string X, X[:i] for all i < n.
    
    Recurrence
    ==========
    LIS(i) = 1 + max(LIS(j)) for all j < i and arr[i] > arr[j].
    
    Running Time
    ============
    For string of length n.
    No. of sub-problems = O(n).
    Time/subprolem = O(n) (check all j's less than i)
    
    Running Time = O(n2).
*/

#include <iostream>
using namespace std;

#define MAX 100

int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
int size = sizeof arr/sizeof arr[0];

int DP[MAX];
int DP1[MAX];

int findMax(int a[], int n) {
    int maxVal = a[0];
    for(int i=1; i<=n; i++)
        if(maxVal < a[i])
            maxVal = a[i];
    return maxVal;
}

//Bottom Up Approach.
int LIS() {
    int i,j,maxVal;
    
    //Every element is a Sequence of length 1.
    for(i=0; i<size; i++)
        DP[i] = 1;
    
    for(i=1; i<size; i++) {
        for(j=0; j<i; j++) {
            if(arr[i] > arr[j]) {
                DP[i] =  max(DP[i] , DP[j] + 1);
            }
        }
    }    
    
    //Pick Maximum of all LIS
    maxVal = findMax(DP,size-1);
    return maxVal;
}

//Top Down Approach.
int LISTopDown(int i) {
    int maxVal;
    if(i==0)
        return 1;
        
    if(DP1[i]) {
        return DP1[i];
    }
    
    for(int j=0; j<i; j++) {
        if(arr[j] < arr[i]) 
            if(LISTopDown(j)+1 > DP1[i]) 
                DP1[i] = LISTopDown(j)+1;
    }
    maxVal = findMax(DP1,i);
    return maxVal;
}

int main() {
    printf("%d",LIS());
    printf("\n%d",LISTopDown(size-1));
    return 0;
}