Advertisement
viligen

longest_incr_subs_DP

Aug 10th, 2022 (edited)
500
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.82 KB | None | 0 0
  1. from collections import deque
  2.  
  3. nums = [int(x) for x in input().split()]
  4.  
  5. size = [0] * len(nums)
  6. size[0] = 1
  7. parent = [None] * len(nums)
  8. best_idx = 0
  9. best_size = 1
  10.  
  11. for curr in range(1, len(nums)):
  12.     curr_num = nums[curr]
  13.     curr_best_size = 1
  14.     curr_parent = None
  15.  
  16.     for prev in range(curr - 1, -1, -1):
  17.         prev_num = nums[prev]
  18.         if prev_num >= curr_num:
  19.             continue
  20.  
  21.         if size[prev] + 1 >= curr_best_size:
  22.             curr_best_size = size[prev] + 1
  23.             curr_parent = prev
  24.     size[curr] = curr_best_size
  25.     parent[curr] = curr_parent
  26.  
  27.     if curr_best_size > best_size:
  28.         best_size = curr_best_size
  29.         best_idx = curr
  30.  
  31. result = deque()
  32.  
  33. while best_idx is not None:
  34.     result.appendleft(nums[best_idx])
  35.     best_idx = parent[best_idx]
  36.  
  37. print(*result)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement