Skip to content

Instantly share code, notes, and snippets.

@suica

suica/construct_max.py

Created January 6, 2023 04:14
Show Gist options
  • Save suica/5f00264490b50a1ffe8841d3a8b0e78a to your computer and use it in GitHub Desktop.
Save suica/5f00264490b50a1ffe8841d3a8b0e78a to your computer and use it in GitHub Desktop.
Download ZIP
construct_max
Raw
construct_max.py
from functools import lru_cache
def construct_max(s: str) -> int:
# run in O(len(s)**2)
@lru_cache(None)
def dp(start, end) -> int:
num_s = int(s[start])
num_e = int(s[end])
if start == end:
return num_s
haha = 10**(end-start)
use_start = num_s * haha + dp(start+1, end)
use_end = num_e * haha + dp(start, end-1)
return max(use_start, use_end)
return dp(0, len(s)-1)
print(construct_max('53123')) # 53321
print(construct_max('001000')) # 1000
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment