java最长凸子序列
注意,我已经看过这个解决方案:Longest convex subsequence in an array
我已经看过上面的解决方案,但我不理解它。我知道的是凸子序列的性质是:
c[i] < (c[i-1] + c[i+1]) / 2
因此,假设输入值为:2082 0 24719 1 383 4 20029 9 3781 16
解决方案是:2082 01 4 9 16
现在,我提出的解决方案是O(n3)
public static int max(int... i){
int max = 0;
for(int n : i){
if(n > max)
max = n;
}
return max;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; ++i)
arr[i] = in.nextInt();
int[][][] LCS = new int[n][n][n];
for(int i = 0; i < n; i++){
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
LCS[i][j][k] = 0;
}
}
}
for(int i = 0; i < arr.length-2; ++i){
for(int j=1; j < arr.length-1;++j){
for(int k = 2; k < arr.length; ++k){
if(arr[j] < (arr[i]+arr[k])/2){
LCS[i][j][k] = max(LCS[i][j][k], 1+ LCS[i][j][k-1]);
}
}
}
}
int max = 0;
for(int i = 0; i < n; ++i) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
if(LCS[i][j][k] > max)
max = LCS[i][j][k];
}
}
}
System.out.println(max);
}
我明白这是完全幼稚的,但我觉得我在正确的轨道上,我不知道为什么,但我一直得到一个序列8的答案。任何帮助都将不胜感激
# 1 楼答案
备忘录中的查找表应该是二维数组。 下面的解决方案也是O(n3)。任何大小为2或更小的序列也是凸子序列。所以,沿着表中的对角线,它将被2填充