Program - A naive Python implementation of LIS problem


Topic: Program - A naive Python implementation of LIS problem

Solution

  
""" 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 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[n-1] is maller 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 
  
    # lenght 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 
  
arr = [10 , 22 , 9 , 33 , 21 , 50 , 41 , 60] 
n = len(arr) 
print ("Length of lis is ", lis(arr) )



List all Python Programs