zjplab
2/6/2017 - 1:53 AM

## Longest Increasing Subsequence

Longest Increasing Subsequence

``````def LIS(arr,n):
lis=[1]*len(arr)
#initialize
for x in lis:
x=1
#compute optimal
for i in range(1,n):
for j in range(0,i-1):
if arr[i]>arr[j] and \
(lis[i]<lis[j]+1):
lis[i]=lis[j]+1
#pick maximum of all LIS values

return max( lis ) ``````
``````/* Dynamic Programming C/C++ implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>

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

/* Initialize LIS values for all indexes */
for (i = 0; i < n; i++ )
lis[i] = 1;

/* Compute optimized LIS values in bottom up manner */
for (i = 1; i < n; i++ )
for (j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;

/* Pick maximum of all LIS values */
for (i = 0; i < n; i++ )
if (max < lis[i])
max = lis[i];

/* Free memory to avoid memory leak */
free(lis);

return max;
}

/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of lis is %d\n", lis( arr, n ) );
return 0;
}``````
``````def LIS(arr,n):

if n==1:#base case
return 1
curr_max=1

for i in range(0,n-1):
subproblem=LIS(arr,i)
if arr[i]<arr[n-1] and \
curr_max < (subproblem +1 ):
curr_max=1 + subproblem

return curr_max

# Driver program to test the functions above
def main():
arr = [10, 22, 9, 33, 21, 50, 41, 60]
n = len(arr)
print ("Length of LIS is", LIS(arr, n))

if __name__=="__main__":
main()

``````
``````
int LIS(int arr[],int n){
//base case
if(n==1) return 1;
//otherwise
int curr_max=1;

for(int i=0;i<n-1;++i){ // i< n-1 because n>=2
while(arr[i]<arr[n-1] ){
int subproblem=LIS(arr,i);
if( (subproblem+1 >curr_max)  )
curr_max=1+subproblem;
}//while ends
}//for ends
return curr_max;
}``````