Mercurial

annotate asyncio_threads/frontend/longest_subinteger.py @ 196:83f16548ba41

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[AI] Adding s3 bucket uploader code using Seobeo.
author MrJuneJune <me@mrjunejune.com>
date Sat, 14 Feb 2026 16:08:15 -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]))