コード
import java.util.Arrays;
public class SubFibonacci {
private final int MAX_F = 46;
public int maxElements(int[] S) {
long[] fib = new long[MAX_F];
fib[0] = 1;
fib[1] = 0;
for (int i = 2; i < fib.length; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
Arrays.sort(S);
int N = S.length;
int[][] max = new int[N][N];
for (int i = 0; i < N; i++) {
max[i][i] = 1;
for (int j = i + 1; j < N; j++) {
for (int a = 0; a < MAX_F - 1; a++) {
for (int b = 0; b < MAX_F - 1; b++) {
if (a == b) {
continue;
}
long y = (long) S[i] * fib[b] - (long) S[j] * fib[a];
y /= (fib[a + 1] * fib[b] - fib[b + 1] * fib[a]);
long x = 0;
if (fib[a] == 0) {
x = S[j] - fib[b + 1] * y;
x /= fib[b];
} else {
x = S[i] - fib[a + 1] * y;
x /= fib[a];
}
if (x <= 0 || y <= 0) {
continue;
}
if (S[i] != fib[a] * x + fib[a + 1] * y) {
continue;
}
if (S[j] != fib[b] * x + fib[b + 1] * y) {
continue;
}
long[] tmpFib = new long[MAX_F];
for (int k = 0; k < MAX_F - 1; k++) {
tmpFib[k] = fib[k] * x + fib[k + 1] * y;
}
int s = i;
int cnt = 0;
for (int k = 0; k < MAX_F - 1; k++) {
while (s < j && tmpFib[k] > S[s]) {
s++;
}
if (tmpFib[k] == S[s]) {
s++;
cnt++;
}
if (s > j) {
break;
}
}
max[i][j] = Math.max(max[i][j], cnt);
}
}
}
}
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
for (int k = j + 1; k < N; k++) {
for (int l = k; l < N; l++) {
ans = Math.max(ans, max[i][j] + max[k][l]);
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
ans = Math.max(ans, max[i][j]);
}
}
return ans;
}
}