fork download
copy 
  1. def preceding_larger(A: list[int]) -> list[int]:
  2.   result = [-1] * len(A)
  3.   stack = []  
  4.  
  5.   for i in range(len(A)):
  6.     while stack and A[stack[-1]] <= A[i]:
  7.       stack.pop()
  8.     if stack:
  9.       result[i] = stack[-1]
  10.     stack.append(i)
  11.  
  12.   return result
  13.  
  14.  
  15. def f(A: list[int]) -> int:
  16.   greaters = preceding_larger(A)
  17.  
  18.   # First in the pair is if A_i is last in a segment,
  19.   # second is if A_i is not last in a segment
  20.   dp = [[0, 0] for _ in A] + [(0, 0)]
  21.  
  22.   for i in range(len(A)):
  23.     # A_i is last
  24.     dp[i][0] = -float('inf') if greaters[i] == -1 else 1 + max(dp[greaters[i] - 1])
  25.  
  26.     # A_i is not last
  27.     if i < len(A) - 1:
  28.       dp[i][1] = max(dp[i - 1])
  29.  
  30.   return max(dp[-2])
  31.  
  32.  
  33. examples = [
  34.   [1, 2, 3, 2, 6, 3],  # 2
  35.   [8, 5, 4, 7, 2],  # 2
  36.   [4, 3, 6, 5, 3, 4, 7, 1],  # 3
  37.   [10, 9, 8, 9, 8, 9, 8, 7],  # 3
  38.   [10, 9, 8, 7, 9, 8, 7, 9, 8, 7],  # 4
  39.   [10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9],  # 1
  40.   [1, 2, 3, 4, 5, 6, 7],  # 0
  41.   [10, 2, 1, 2, 1, 2, 1, 9, 8, 7] # 4
  42. ]
  43.  
  44. for A in examples:
  45.   print((A, f(A)))
Success #stdin #stdout 0.11s 14188KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
([1, 2, 3, 2, 6, 3], 2)
([8, 5, 4, 7, 2], 2)
([4, 3, 6, 5, 3, 4, 7, 1], 3)
([10, 9, 8, 9, 8, 9, 8, 7], 3)
([10, 9, 8, 7, 9, 8, 7, 9, 8, 7], 4)
([10, 5, 6, 4, 7, 6, 4, 2, 7, 1, 4, 6, 3, 4, 5, 1, 7, 5, 4, 6, 7, 8, 4, 6, 1, 9, 9], 1)
([1, 2, 3, 4, 5, 6, 7], 0)
([10, 2, 1, 2, 1, 2, 1, 9, 8, 7], 4)
https://ideone.com/OFwoio
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

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!