Advertisement
viligen

connecting_cables_DP

Aug 10th, 2022
522
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.43 KB | None | 0 0
  1. cables = [int(x) for x in input().split()]
  2.  
  3. positions = sorted(cables)
  4.  
  5. size = len(cables) + 1
  6. lcs = [[0] * size for _ in range(size)]
  7.  
  8. for row in range(1, size):
  9.     for col in range(1, size):
  10.         if cables[row-1] == positions[col-1]:
  11.             lcs[row][col] = lcs[row-1][col-1] + 1
  12.         else:
  13.             lcs[row][col] = max(lcs[row-1][col], lcs[row][col-1])
  14.  
  15. print(f'Maximum pairs connected: {lcs[size-1][size-1]}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement