找出序列中最长的等差数列 [英] Find the longest arithmetic progression inside a sequence

问题描述

假设我有一个数字递增的序列，我想找到序列中最长等差数列的长度.最长等差数列是指具有共同差异的递增序列，例如 [2, 4, 6, 8] 或 [3, 6, 9, 12].

Suppose I have a sequence of increasing numbers, and I want to find the length of longest arithmetic progression within the sequence. Longest arithmetic progression means an increasing sequence with common difference, such as [2, 4, 6, 8] or [3, 6, 9, 12].

例如，对于[5, 10, 14, 15, 17]，[5, 10, 15]是最长的等差数列，长度为3；

For example, for [5, 10, 14, 15, 17], [5, 10, 15] is the longest arithmetic progression, with length 3;

对于[10, 12, 13, 20, 22, 23, 30]，[10, 20, 30]是最长的等差数列，长度为3；

for [10, 12, 13, 20, 22, 23, 30], [10, 20, 30] is the longest arithmetic progression with length 3;

对于 [7, 10, 12, 13, 15, 20, 21], [10, 15, 20] 或 [7, 10,13] 是最长的等差数列，长度为 3.

for [7, 10, 12, 13, 15, 20, 21], [10, 15, 20] or [7, 10, 13] are the longest arithmetic progressions with length 3.

本站https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_eticLongestjsp提供对问题的一些见解，即通过循环 j 并考虑每 3 个元素.我打算在Python中使用这个算法，我的代码如下:

This site https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp offers some insight into the problem, i.e. by looping around j and consider every 3 elements. I intend to use this algorithm in Python, and my code is as follows:

def length_of_AP(L):
n = len(L)
Table = [[0 for _ in range(n)] for _ in range(n)]
length_of_AP = 2

# initialise the last column of the table as all i and (n-1) pairs have lenth 2
for i in range(n):
        Table[i][n-1] =2

# loop around the list and i, k such that L[i] + L[k] = 2 * L[j]
for j in range(n - 2, 0, -1):
        i = j - 1
        k = j + 1
        while i >= 0 and k < n:
                difference = (L[i] + L[k]) - 2 * L[j]
                if difference < 0:
                        k = k + 1
                else:
                        if difference > 0:
                                i = i - 1
                        else:
                                Table[i][j] = Table[j][k] + 1
                                length_of_AP = max(length_of_AP, Table[i][j])
                                k = k + 1
                                i = i - 1
return length_of_AP

这个函数对 [1, 3, 4, 5, 7, 8, 9] 很好，但对 [5, 10, 14, 15, 20, 25, 26, 27, 28,30, 31]，我应该得到 6，但我得到了 4.我可以看到原因是列表中的 25、26、27、28 可能是我的功能分散注意力的因素.我如何更改我的函数，以便它给我想要的结果.

This function works fine with [1, 3, 4, 5, 7, 8, 9], but it doesn't work for [5, 10, 14, 15, 20, 25, 26, 27, 28, 30, 31], where I am supposed to get 6 but I got 4. I can see the reason being that 25, 26, 27, 28 inside the list may be a distracting factor for my function. How do I change my function so that it gives me the result desired.

如有任何帮助，我们将不胜感激.

Any help may be appreciated.

推荐答案

按照您的链接并运行第二个示例，看起来代码实际上找到了合适的 LAP

Following your link and running second sample, it looks like the code actually find proper LAP

5, 10, 15, 20, 25, 30,

5, 10, 15, 20, 25, 30,

但未能找到合适的长度.我没有花太多时间分析代码而是分析代码

but fails to find proper length. I didn't spend too much time analyzing the code but the piece

    // Any 2-letter series is an AP
    // Here we initialize only for the last column of lookup because
    // all i and (n-1) pairs form an AP of size 2  
    for (int i=0; i<n; i++)
        lookup[i][n-1] = 2;

对我来说看起来很可疑.似乎您需要用 2 而不是最后一列来初始化 whole lookup 表，如果我这样做，它也会开始在您的样本上获得正确的长度.

looks suspicious to me. It seems that you need to initialize whole lookup table with 2 instead of just last column and if I do so, it starts to get correct length on your sample as well.

因此摆脱初始化"循环并将第三行更改为以下代码:

So get rid of the "initialise" loop and change your 3rd line to following code:

# initialise whole table with 2 as all (i, j) pairs have length 2    
Table = [[2 for _ in range(n)] for _ in range(n)]

此外他们的

示例执行:
最大 AP 长度 = 6
3, 5, 7, 9, 11, 13, 15, 17,

Sample Execution:
Max AP length = 6
3, 5, 7, 9, 11, 13, 15, 17,

也包含此错误，并且仅由于运气而实际打印正确的序列.如果我将 sortedArr 修改为

Contains this bug as well and actually prints correct sequence only because of sheer luck. If I modify the sortedArr to

int sortedArr[] = new int[] {3, 4, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 18,  112, 113, 114, 115, 116, 117, 118};

我得到以下输出

最大 AP 长度 = 7
112, 113, 114, 115, 116, 117, 118,

Max AP length = 7
112, 113, 114, 115, 116, 117, 118,

这显然是错误的，因为原来的 8 项长序列 3,5,7,9,11,13,15,17, 仍然存在.

which is obviously wrong as original 8-items long sequence 3, 5, 7, 9, 11, 13, 15, 17, is still there.

这篇关于找出序列中最长的等差数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！