为什么我的代码找不到最长算术子序列的长度?

Question

问题是在一个算术性质的数组中找到子序列的长度。这个问题可以在leetcode上找到。

我的代码是:

def longestArithSeqLength(self, nums: List[int]) -> int:
if len(nums)==1:
return 1
dp = []
for i in nums:
dp.append(dict())
max_so_far = 1
for i in range(1,len(nums)):
for j in range(i-1,-1,-1):
difference = nums[i] - nums[j]
if difference in dp[j]:
dp[i][difference] = dp[j][difference]+1
max_so_far = max(max_so_far,dp[i][difference]+1)        
else:
dp[i][difference] = 1
max_so_far = max(max_so_far,dp[i][difference]+1)
return max_so_far

在这里，在每个索引处，我都有一个字典来计算子序列1的长度，直到该索引与前一个元素的每个差异。但是对于一个测试用例，我的代码失败了:

[22,8,57,41,36,46,42,28,42,14,9,43,27,51,0,0,38,50,31,60,29,31,20,23,37,53,27,1,47,42,28,31,10,35,39,12,15,6,35,31,45,21,30,19,5,5,4,18,38,51,10,7,20,38,28,53,15,55,60,56,43,48,34,53,54,55,14,9,56,52]

我完全不知道为什么会发生这种事。有人可以解释我的逻辑是错误的，为什么它不能处理这个测试用例?

Answer 1

我现在知道我错了。在第j个循环中，我从右到左开始，所以如果再次看到差异，将更新左边的长度而不是右边的长度。这可能听起来令人困惑，但让我解释一下。

对于序列-2，-1,0,10，-3，-2，-1,0,1,2

当我在元素1(带有循环元素)处，并且从0迭代到-2(在第j个循环中从右向左)，当它第一次看到0时，它将差1更新为第0个(第二个零)字典中的差1 +1。然后它转到左侧0，再次看到差异1，并将差异1更新为第0个元素(第一个)的字典值1，它的子序列长度小于第二次出现。因此，如果我只是从左到右而不是从右到左运行循环，这就解决了问题。

代码现在看起来像:

def longestArithSeqLength(self, nums: List[int]) -> int:
if len(nums)==1:
return 1
dp = []
for i in nums:
dp.append(dict())
max_so_far = 1
for i in range(1,len(nums)):
####   RUNNNING LOOP LEFT TO RIGHT NOW   ####
for j in range(i):
difference = nums[i] - nums[j]
if difference in dp[j]:
dp[i][difference] = dp[j][difference]+1
max_so_far = max(max_so_far,dp[i][difference]+1)        
else:
dp[i][difference] = 1
max_so_far = max(max_so_far,dp[i][difference]+1)
return max_so_far

Answer 2

def longestArithSeqLength(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
dp = []
for i in nums:
dp.append(dict())
max_so_far = 0  # Initialize max_so_far to 0 instead of 1
for i in range(1, len(nums)):
for j in range(i-1, -1, -1):
difference = nums[i] - nums[j]
if difference in dp[j]:
dp[i][difference] = dp[j][difference] + 1
max_so_far = max(max_so_far, dp[i][difference])  # Update max_so_far without adding 1
else:
dp[i][difference] = 1
max_so_far = max(max_so_far, dp[i][difference])
return max_so_far + 1  # Add 1 to max_so_far to account for the current element