python動的計画問題------最長上昇サブシーケンス個数を求める

4092 ワード


def len_of_longest_ascending_subsequences(nums):
		if len(nums)<=1:
			return len(nums)
		#                   
		mem = [0 for _ in range(len(nums))]

		for j in range(1,len(nums)):
			for i in range(0,j):
				# 1<2
				if nums[i]<nums[j]:
					# max(1,1+1)
					#                 
					#       
					mem[j] = max(mem[j],mem[i]+1)
					# mem[1] = 2
		print(mem)

		return max(mem)
# list01=[2,-5,-6,-8,-3,3,56,6,3,6,7,100,9,3]
list01=[1,2,6,3]
print(len_of_longest_ascending_subsequences(list01))