Mercurial

annotate asyncio_threads/frontend/longest_subinteger.py @ 71:75de5903355c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Giagantic changes that update Dowa library to be more align with stb style array and hashmap. Updated Seobeo to be caching on server side instead of file level caching. Deleted bunch of things I don't really use.
author June Park <parkjune1995@gmail.com>
date Sun, 28 Dec 2025 20:34:22 -0800
parents 46daba6e3cf4
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
48
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
1 # Analyze a given array of integers and write a function to determine the length of the longest subsequent growing sequence contained within the array.
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
2
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
3
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
4 # 1,2,3,4,2,1,3
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
5 # |
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
6
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
7 # Example 1:
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
8 #
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
9 # Input: nums = [10,9,2,5,3,7,101,18]
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
10 # [(2, 1), 3, 5, 7, 9, 10, 18, 101]
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
11 # |
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
12 # Output: 4
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
13
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
14 # Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
15
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
16 # Example 2:
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
17 #
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
18 # Input: nums = [0,1,0,3,2,3]
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
19 # Output: 4
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
20 # Example 3:
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
21 #
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
22 # Input: nums = [7,7,7,7,7,7,7]
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
23 # Output: 1
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
24
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
25
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
26 # Longest Increasing Subsequence
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
27 def main(nums):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
28 ans = 0
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
29 cache = set()
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
30
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
31 def dfs(val, pos, curr_ans):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
32 nonlocal ans
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
33
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
34 if ((val, pos, curr_ans) in cache):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
35 return
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
36
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
37 if pos > len(nums):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
38 return
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
39 if nums[pos] > val:
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
40 curr_ans += 1
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
41 else:
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
42 ans = max(ans, curr_ans)
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
43 return
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
44 for i in range(pos, len(nums)):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
45 dfs(nums[pos], i, curr_ans)
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
46
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
47 for i in range(len(nums)):
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
48 dfs(float("-inf"), i, 0)
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
49
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
50 return ans
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
51
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
52
46daba6e3cf4 Few python scrtips to show how to use asychio.
MrJuneJune <me@mrjunejune.com>
parents:
diff changeset
53 print(main([10,9,2,5,3,7,101,18]))