비어 있지 않은 유한 한 정수 시퀀스가 주어지면 최대 길이의 산술 부분 시퀀스를 반환합니다.
동일한 최대 길이의 배수가 여러 개 있으면 모두 반환 될 수 있습니다.
정의 :
연산 시퀀스는 시퀀스이다 a(1),a(2),a(3),a(4),...
상수가되도록 c
그러한 a(m+1)-a(m) = c
모든이 m
. 다시 말해서 : 두 개의 후속 항의 차이는 일정합니다.
시퀀스 감안할 때 서브는 순서입니다 및 모든 . 다시 말해 : 원래 순서대로 가져 가서 원하는만큼 항목을 제거하십시오.b(1),b(2),b(3),b(4),...
b(s(1)),b(s(2)),b(s(3)),b(s(4)),...
1 <= s(1)
s(m) < s(m+1)
m
예
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]
더 긴 테스트 사례 :
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]
배경
나는 2004 년부터 Green-Tao-Theorem을 떠 올렸을 때이 아이디어를 얻었다.
답변
젤리 , 8 바이트
ŒPIE$ÐfṪ
온라인으로 사용해보십시오! 또는 모든 테스트 사례를 확인하십시오 .
작동 원리
Œ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 바이트
ef!P{-VTtTy
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
바이트에 대한 @LeakyNun 에게 감사합니다 !
답변
MATL, 19 18 17 16 18 바이트
Luis 덕분에 1 바이트가 절약되고 2 바이트가 다시 추가되었습니다!
"GX@XN!"@dun2<?vx@
무차별 대입법은 입력의 모든 순서 순열을 검사하는 상당히 순진한 접근 방식입니다. 분명히 더 긴 시퀀스에는 시간이 걸릴 수 있습니다. 바이트를 저장하기 위해 가장 작은 하위 시퀀스 (길이 = 1)로 시작하여 더 큰 시퀀스 (길이 = N)까지 작업했습니다.
설명
% 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
답변
파이썬 2 124 115 98 97 바이트
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)
매우 느리고 메모리 집약적입니다. Ideone에서 테스트하십시오 .
대체 버전, 98 바이트
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)
이로써 모든 테스트 사례가 즉시 완료됩니다. Ideone에서 테스트하십시오 .
답변
Pyth Checkout 8593c76, 3 월 24 일 , 10 바이트
efq-VTtT)y
이 행진에서 그 뒤로 제외하고, 정확하게 손잡이의 대답과 동일, 2 바이트 기능 (거기 q ... )
같은 인 동일이었다리스트의 모든 요소 여부 확인), !P{
당신이 할 수있는 최선이다, 현재
답변
자바 스크립트 (ES6), 157 바이트
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)}
젤리 답변보다 거의 20 배 길다 … 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;
}