fork download
copy 
  1. def solve_lis(arr):
  2.     n = len(arr)
  3.     best = [0] * (n+1)
  4.     best[n-1] = 1
  5.  
  6.     # step 1 we'll compute the best array using Dynamic Programming
  7.     for i in range(n-2, -1, -1):
  8.         max = 0
  9.         temp = arr[i]
  10.         for j in range(i+1, n):
  11.             if arr[j] > arr[i] and best[j] > max:
  12.                 max = best[j]
  13.         best[i] = 1 + max
  14.  
  15.     maxEl = best[0]
  16.     maxPos = 0
  17.     for i in range(1, n):
  18.         if best[i] > maxEl:
  19.             maxEl = best[i]
  20.             maxPos = i
  21.     print(arr[maxPos], end = " ")
  22.     maxEl -= 1
  23.     for k in range(maxPos+1, n):
  24.         if best[k] == maxEl and arr[maxPos] < arr[k]:
  25.             print("%d "%arr[k], end =" ")
  26.             maxEl-=1
  27. def func():
  28.     # let we have the following array
  29.     arr = [10, 22, 9, 33, 21, 50, 41, 60, 80]
  30.  
  31.     solve_lis(arr)
  32.  
  33. func()
  34.  
Success #stdin #stdout 0.04s 9576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 22  33  50  60  80
https://ideone.com/LmeaX5
LIS
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!