Étant donné une séquence finie non vide d'entiers, retournez une sous-séquence arithmétique de longueur maximale.

S'il y a plusieurs de la même longueur maximale, n'importe lequel d'entre eux peut être retourné.

Définitions:

Une séquence arithmétique est une séquence a(1),a(2),a(3),a(4),...telle qu'il existe une constante ctelle que a(m+1)-a(m) = cpour tous m. En d'autres termes: la différence entre deux termes suivants est constante.

Étant donné une séquence, b(1),b(2),b(3),b(4),...une sous -séquence est une séquence b(s(1)),b(s(2)),b(s(3)),b(s(4)),...où 1 <= s(1)et s(m) < s(m+1)pour tous m. En d'autres termes: prenez la séquence d'origine et supprimez autant d'entrées que vous le souhaitez.

Exemples

Input                     Output
[4,1,2,3,6,5]             [1,3,5] or [1,2,3]
[5,4,2,-1,-2,-4,-4]       [5,2,-1,-4]
[1,2,1,3,1,4,1,5,1]       [1,1,1,1,1] or [1,2,3,4,5]
[1]                       [1]

Quelques cas de test plus longs:

Length: 25
Input: [-9,0,5,15,-1,4,17,-3,20,13,15,9,0,-6,11,17,17,9,26,11,5,11,3,16,25]
Output: [15,13,11,9] or [17,13,9,5]

Length: 50
Input: [35,7,37,6,6,33,17,33,38,30,38,12,37,49,44,5,19,19,35,30,40,19,11,5,39,11,20,28,12,33,25,8,40,6,15,12,27,5,21,6,6,40,15,31,49,22,35,38,22,33]
Output: [6,6,6,6,6] or [39,33,27,21,15]

Length: 100
Input: [6,69,5,8,53,10,82,82,73,15,66,52,98,65,81,46,44,83,9,14,18,40,84,81,7,40,53,42,66,63,30,44,2,99,17,11,38,20,49,34,96,93,6,74,27,43,55,95,42,99,31,71,67,54,70,67,18,13,100,18,4,57,89,67,20,37,47,99,16,86,65,38,20,43,49,13,59,23,39,59,26,30,62,27,83,99,74,35,59,11,91,88,82,27,60,3,43,32,17,18]
Output: [6,18,30,42,54] or [8,14,20,26,32] or [46,42,38,34,30] or [83,63,43,23,3] or [14,17,20,23,26] or [7,17,27,37,47] or [71,54,37,20,3]

Contexte

J'ai eu cette idée lorsque j'ai rappelé le théorème de Green-Tao de 2004, qui stipule que la séquence de nombres premiers contient des séquences arithmétiques finies de longueur arbitraire.

Gelée , 8 octets

ŒPIE$ÐfṪ

Essayez-le en ligne! ou vérifiez tous les cas de test .

Comment ça fonctionne

ŒPIE$ÐfṪ  Main link. Argument: A (list of integers)

ŒP        Powerset; generate all sublists of A, sorted by length.
     Ðf   Filter the powerset by the link to the left:
    $       Combine the two atoms to the left into a monadic link.
  I           Compute all increments.
   E          Test whether they're all equal.
          This returns all arithmetic subsequences, sorted by length.
       Ṫ  Tail; extract the last sequence.

Pyth, 12 11 octets

ef!P{-VTtTy

Suite de tests.

          y  powerset of implicit input, generate all subsequences
ef       T   find the last subsequence (sorted increasing in length) where...
       Tt      bifurcate over tail, giving [1,2,3,4,5] [2,3,4,5]
     -V        vectorize over -, giving differences of each consecutive pair
    {          dedup (remove duplicate elements)
   P           pop, resulting in [] if all differences were equal
  !            boolean not, resulting in True if all differences were equal

Merci à @LeakyNun pour un octet!

MATL, 19 18 17 16 18 octets

1 octet enregistré (et 2 octets ajoutés en arrière) grâce à Luis!

"GX@XN!"@dun2<?vx@

Une approche assez naïve où la force brute vérifie toutes les permutations ordonnées de l'entrée. Évidemment, cela peut prendre un certain temps pour les séquences plus longues. Pour enregistrer un octet, j'ai commencé avec les plus petites sous-séquences (longueur = 1) et j'ai travaillé jusqu'aux séquences plus grandes (longueur = N).

Essayez-le en ligne!

Explication

                % Impilicitly grab input array (N)
"               % For each value in this array
    G           % Explicitly grab the input
    X@          % Loop index, will be [1, 2, ... length(N)] as we iterate
    XN          % Determine all permutations of k elements (nchoosek). The output is 
                % each k-length permutation of the input as a different row. Order doesn't 
                % matter so the result is always ordered the same as the input
    !           % Take the transpose so each k-length permutation is a column
    "           % For each column
        d       % Compute the difference between successive elements
        un      % Determine the number of unique differences
        2<?     % If there are fewer than 2 unique values
            vx  % Vertically concatenate everything on the stack so far and delete it
            @   % Push the current permuatation to the stack
                % Implicit end of if statement
                % Implicit end of for loop
                % Implicit end of for loop
                % Implicitly display the stack

Python 2, 124 115 115 98 97 octets

p=[[]]
for n in input():p+=[x+[n][:2>len(x)or n-x[-1]==x[1]-x[0]]for x in p]
print max(p,key=len)

Très lent et gourmand en mémoire. Testez-le sur Ideone .

Version alternative, 98 octets

p={()}
for n in input():p|={x+(n,)[:2>len(x)or n-x[-1]==x[1]-x[0]]for x in p}
print max(p,key=len)

Cela termine instantanément tous les cas de test. Testez-le sur Ideone .

Checkout Pyth 8593c76, 24 mars , 10 octets

efq-VTtT)y

C'est exactement la même chose que la réponse de Doorknob, sauf qu'en mars, il y avait une fonction de 2 octets ( q ... )) qui vérifiait si tous les éléments d'une liste étaient les mêmes, ce qui est le même que !P{, ce qui est le mieux que vous puissiez faire actuellement.

JavaScript (ES6), 157 octets

a=>{for(m=i=0,l=a.length;i<l;i++)for(j=i;++j<l;)for(t=n=a[k=i],c=0;k<l;k++)a[k]==t&&(t+=a[j]-n,++c>m)?q=a[m=c,p=n,j]-n:q;return a.slice(-m).map(_=>(p+=q)-q)}

Presque 20 fois plus longtemps que la réponse Jelly ... Non golfée:

function subsequence(a) {
    var max = 0;
    for (var i = 0; i < a.length; i++) {
        for (var j = i + 1; j < a.length; j++) {
            var target = a[i];
            var count = 0;
            for (var k = i; k < a.length; k++) {
                if (a[k] == target) {
                    count++;
                    target += a[j] - a[i];
                    if (count > max) {
                        max = count;
                        start = a[i];
                        step = a[j] - a[i];
                    }
                }
            }
        }
    }
    var result = new Array(max);
    for (var i = 0; i < max; i++) {
        result[i] = start + step * i;
    }
    return result;
}