fork download
copy 
  1. #
  2. # Dynamic Programming
  3. #
  4. def find_lis(arr):
  5.  
  6.     n = len( arr )
  7.  
  8.     best = [0] * (n)
  9.     best[n-1] = 1
  10.  
  11.     # we will create the best array
  12.     for i in range(n-2, -1, -1):
  13.         aux = arr[i]
  14.         max = 0
  15.         for j in range(i+1, n):
  16.             if arr[j] > aux and best[j] > max:
  17.                 max = best[j]
  18.         best[i] = 1 + max
  19.     maxBest = best[0]
  20.     posMax = 0
  21.     for i in range(1, n):
  22.         if best[i]>maxBest:
  23.             maxBest = best[i]
  24.             posMax = i
  25.     print(best)
  26.     print(maxBest, posMax)
  27.     print(arr[posMax], end = " ")
  28.     pos = maxBest
  29.     pos-=1
  30.     for i in range(posMax+1, n):
  31.         if best[i] == pos and arr[i] > arr[posMax]:
  32.             print(arr[i], end = " ")
  33.             pos-=1
  34.  
  35. def gokyo():
  36.  
  37.     arr = [24,12,15,15,19]
  38.     print(arr)
  39.     find_lis(arr)
  40.  
  41. gokyo()
  42.  
Success #stdin #stdout 0.04s 9612KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[24, 12, 15, 15, 19]
[1, 3, 2, 2, 1]
3 1
12 15 19
https://ideone.com/agCtO9
Finding longest increasing subsequence.
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!