-
Notifications
You must be signed in to change notification settings - Fork 9
/
Longest_Increasing_Subsequence.py
65 lines (45 loc) · 1.49 KB
/
Longest_Increasing_Subsequence.py
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# A naive Python implementation of LIS problem
""" To make use of recursive calls, this function must return
two things:
1) Length of LIS ending with element arr[n-1]. We use
max_ending_here for this purpose
2) Overall maximum as the LIS may end with an element
before arr[n-1] max_ref is used this purpose.
The value of LIS of full array of size n is stored in
*max_ref which is our final result """
# global variable to store the maximum
global maximum
def _lis(arr, n):
# to allow the access of global variable
global maximum
# Base Case
if n == 1:
return 1
# maxEndingHere is the length of LIS ending with arr[n-1]
maxEndingHere = 1
"""Recursively get all LIS ending with arr[0], arr[1]..arr[n-2]
IF arr[i-1] is smaller than arr[n-1], and max ending with
arr[n-1] needs to be updated, then update it"""
for i in range(1, n):
res = _lis(arr, i)
if arr[i-1] < arr[n-1] and res+1 > maxEndingHere:
maxEndingHere = res + 1
# Compare maxEndingHere with overall maximum. And
# update the overall maximum if needed
maximum = max(maximum, maxEndingHere)
return maxEndingHere
def lis(arr):
# to allow the access of global variable
global maximum
# length of arr
n = len(arr)
# maximum variable holds the result
maximum = 1
# The function _lis() stores its result in maximum
_lis(arr, n)
return maximum
# Driver program to test the above function
arr = [10, 22, 9, 33, 21, 50, 41, 60]
n = len(arr)
print ("Length of lis is ", lis(arr))
# This code is contributed by NIKHIL KUMAR SINGH