在Python中查找给定列表的最长算术子序列长度
假设我们有一个名为nums的数字列表,我们必须找到最长算术子序列的长度。我们知道,当S[i+1] – S[i]对于范围内的每个i(0 ≤ i < S大小- 1)具有相同的值时,序列S[i]是等差数列。
因此,如果输入是nums = [1, 4, 7, 10, 13, 20, 16],那么输出将是6,子序列[1, 4, 7, 10 , 13, 16]是算术序列,因为每个相邻元素之间的差为3。
为了解决这个问题,我们将遵循以下步骤:
- n := arr的大小
- 如果n <= 1,则
- 返回n
- res := 0
- dp :=空映射,默认情况下,当未找到key时,它将存储1
- for i在范围1到n – 1中,执行
- for j在范围0到i – 1中执行
- diff := arr[i] – arr[j]
- dp[i,diff] := dp[j,diff] + 1
- res := res和dp[I,diff之间的最大值
- for j在范围0到i – 1中执行
- 返回res
更多Python相关文章,请阅读:Python 教程
示例(Python)
让我们看下面的实现以获得更好的理解:
from collections import defaultdict
class Solution:
def solve(self, arr):
n = len(arr)
if n <= 1:
return n
res = 0
dp = defaultdict(lambda: 1)
for i in range(1, n):
for j in range(i):
diff = arr[i] - arr[j]
dp[i, diff] = dp[j, diff] + 1
res = max(res, dp[i, diff])
return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))
输入
[1, 4, 7, 10, 13, 20, 16]
输出
6