Return to Question

###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

###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.

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

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.

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]

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]

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]

###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.

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:

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.