11
\$\begingroup\$

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.

Definitions:

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.

Examples

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]

Background

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.

\$\endgroup\$
5
\$\begingroup\$

Jelly, 8 bytes

ŒPIE$ÐfṪ

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pyth, 12 11 bytes

ef!P{-VTtTy

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

MATL, 19 18 17 16 18 bytes

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

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

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!

Explanation

                % 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
| improve this answer | |
\$\endgroup\$
  • \$\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
1
\$\begingroup\$

Python 2, 124 115 98 97 bytes

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)

Very slow and memory intensive. Test it on Ideone.

Alternate version, 98 bytes

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)

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ byte or speed, that is the question \$\endgroup\$ – downrep_nation May 29 '16 at 9:06
0
\$\begingroup\$

Pyth checkout 8593c76, March 24th, 10 bytes

efq-VTtT)y

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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) {
                    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;
}
| improve this answer | |
\$\endgroup\$

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.