# Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点,从前到后,但只能从低处往高处的桩子走。他希望走的步数最多,
# 你能替Redraiment研究他最多走的步数吗?
#
# 数据范围:每组数据长度满足 1≤n≤200 , 数据大小满足 1≤val≤350
# 输入描述:
# 数据共2行,第1行先输入数组的个数,第2行再输入梅花桩的高度
# 输出描述:
# 输出一个结果
def raiment(num):
# 方法1
num_list = list(num.split())
dict1 = dict()
for i in range(0, len(num_list) - 1):
temp = num_list[i]
temp2 = num_list[i]
cnt = 1
for j in range(i + 1, len(num_list)):
if int(num_list[j]) > int(temp):
temp2 = temp
temp = num_list[j]
cnt += 1
continue
else:
if int(temp2) < int(num_list[j]) < int(temp):
temp = num_list[j]
dict1.update({f"from {i}: ": cnt})
return dict1, max(dict1.values())
def raiment2(num):
# 方法2: 扫描 i 前面的桩,如果有比 i 小的话就使用状态转移方程 dp[i] = max(dp[i], dp[j] + 1)
num_list = list(num.split())
dp = [1] * len(num_list)
for i in range(len(num_list)):
for j in range(i):
if num_list[j] < num_list[i]:
dp[i] = max(dp[i], dp[j] + 1)
return dp, max(dp)
if __name__ == '__main__':
num = "2 5 1 5 4 5"
dict1, num1 = raiment(num)
print(num1)