LONGEST INCREASING SUBSEQUENCE - DYNAMIC PROGRAMMING

//LONGEST INCREASING SUBSEQUENCE - DYNAMIC PROGRAMMING APPROACH - O(n^2)

#include<iostream>
#include<conio.h>
#include<stdlib.h>

using namespace std;

//lis() returns length of longest increasing subsequence in arr[] of size n
int lis(int arr[], int n)
{
    int* lis, i, j, max = 0;
    lis = ( int * )malloc( sizeof(sizeof(int)* n) ) ;

    //initialise lis values for all indexes
    for (int i = 0; i < n; ++i)
        lis[i] = 0;

    //bottom up uproach for dynamically calculating optimized LIS value
    for (int i = 1; i < n; ++i)
    for (int j = 0; j < i; ++j)
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1)
        //update lis[i]
        lis[i] = lis[j] + 1;

    //pick max of lis values
    for (i = 0; i < n; ++i)
    if (max < lis[i])
        max = lis[i];
   

    //free memory avoiding memory leaks
    free(lis);

    return max;


 }



int main()
{

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

    printf("Lenght of LIS is %d \n ", lis(arr, n));

    getchar();

    return 0;
}