这道题我做的方法用了n2 的时间复杂度 太麻烦了
官方解答里用了 n的时间复杂度
一开始没看懂 这里详细解释一下
假设有一个序列
1 2 3 4 5 6 7 8 9
包含6 的长度为奇数的子序列有多少个？
6左边有5个数字 右边有3个数字
首先不看这个问题 写一个表格 加入某个数字在一个子序列里，不同长度下 左右两侧的数字分别有多少个：
长度为1： 0-0
长度为3：0-2 1-1 2-0
长度为5：0-4 1-3 2-2 3-1 4-0
长度为7：0-6 1-5 2-4 3-3 4-2 5-1 6-0
对于6而言 只满足这几种情况
0-0 0-2 和 2-0 2-2 和 4-0 4-2
1-1 1-3 和 3-1 3-3 和 5-1 5-3
左侧为偶数的 不能超过5 右侧为偶数的不能超过3
左侧为奇数的 不能超过5 右侧为奇数的 不能超过3
所以一共是
((5+1)//2 )((3+1)//2) + (5//2+1)(3//2+1) =32+32=12种
所有的数字都可以这么算 最后就得到答案了
这种方法只需要 n的时间复杂度