Given a non empty finite sequence of integers, return an arithmetic subsequence of maximal length.

If there are multiple of the same maximal length, any of them can be returned.


An arithmetic sequence is a sequence \$a(1),a(2),a(3),a(4),...\$ such that there is a constant \$c\$ such that \$a(m+1)-a(m) = c\$ for all \$m\$. In other words: The difference between two subsequent terms is constant.

Given a sequence \$b(1),b(2),b(3),b(4),...\$ a subsequence is a sequence \$b(s(1)),b(s(2)),b(s(3)),b(s(4)),...\$ where \$1 <= s(1)\$ and \$s(m) < s(m+1)\$ for all \$m\$. In other words: Take the original sequence and remove as many entries as you want.


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]

Some longer test cases:

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]


I got this idea when I recalled the Green-Tao-Theorem from 2004, which states that the sequence of primes contains finite arithmetic sequences of arbitrary length.


Jelly, 8 bytes


Try it online! or verify all test cases.

How it works

Œ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 bytes


Test suite.

          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

Thanks to @LeakyNun for a byte!


MATL, 19 18 17 16 18 bytes

1 byte saved (and 2 bytes added back) thanks to Luis!


A fairly naive approach which brute force checks all ordered permutations of the input. Obviously this can take a while for longer sequences. To save a byte, I have started with the smallest sub-sequences (length = 1) and worked up to the larger sequences (length = N).

Try it Online!


                % 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
  • \$\begingroup\$ @LuisMendo Thanks! I always wondered how to get the loop iteration #. \$\endgroup\$
    – Suever
    May 29 '16 at 3:45
  • \$\begingroup\$ @LuisMendo Oh good catch, you're right. That double diff gives an empty array which can't be negated. \$\endgroup\$
    – Suever
    May 29 '16 at 4:01

Husk, 6 bytes


Try it online!


The return value of E is useful here for getting the longest list that satisfies a condition.

►oEẊ-Ṗ   Implicit argument: a list.
     Ṗ   List of all its subsequences.
►        Find one that maximizes:
 o        Composition of two functions:
   Ẋ       1. Apply to adjacent elements:
    -         Subtraction.
  E        2. Are all elements equal?
              Returns length+1 if they are, 0 if not.

Python 2, 124 115 98 97 bytes

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)

Very slow and memory intensive. Test it on Ideone.

Alternate version, 98 bytes

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)

This completes all test cases instantly. Test it on Ideone.

  • 1
    \$\begingroup\$ byte or speed, that is the question \$\endgroup\$ May 29 '16 at 9:06

Pyth checkout 8593c76, March 24th, 10 bytes


This is exactly the same as Doorknob's answer, except that back in march, there was a 2 byte function (q ... )) which checked whether all of the elements of a list were the same, which is the same as !P{, which is the best you can do currently.


JavaScript (ES6), 157 bytes

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)}

Almost 20 times longer than the Jelly answer... Ungolfed:

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) {
                    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;

Japt -h, 13 bytes

à ñÊkÈän än d

Try it


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.