forked from AllAlgorithms/cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlis.cpp
More file actions
39 lines (32 loc) · 1 KB
/
lis.cpp
File metadata and controls
39 lines (32 loc) · 1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}
int main()
{
/* Driver program to find Longest Increasing Subsequence */
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of lis is %d", lis( arr, n ) );
return 0;
}