python-programs/subsequence.py at master · kumaya/python-programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
defsubsequence(inp, s, out, count):
ifs==len(inp):
count[0] =max(count[0], len(out))
return
foriinrange(s, len(inp)):
iflen(out) >0andout[-1] >=inp[i]:
count[0] =max(count[0], len(out))
continue
subsequence(inp, i+1, out+[inp[i]], count)


defsubsequenceDP(nums):
dp= [0]*len(nums)
dp[0] =1
foriinrange(1, len(nums)):
tmp=0
forjinrange(0, i):
ifnums[i] >nums[j]:
tmp=max(tmp, dp[j])
dp[i] =tmp+1
print(dp)
returnmax(dp)


if__name__=='__main__':
inp= [10,9,2,5,3,7,101,18]
# inp = [0,1,0,3,2,3]

# inp = [7,7,7,7,7,7,7]
inp=[1,3,6,7,9,4,10,5,6]
c= [0]
subsequence(inp, 0, [], c)
print (c[0])

print(subsequenceDP(inp))