最長凸部分列

Question

注、私はすでにこのソリューションを見て：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 0 1 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の等価。どんな助けもありがとう。

Answer 1

Memoizationのルックアップテーブルは、2次元配列でなければなりません。 下の解もO（n3）です。サイズ2以下のシーケンスも凸状の部分シーケンスです。したがって、テーブルの対角線に沿って、2で塗りつぶされます。

import java.util.Scanner; 

public class LongestConvexSubSequence { 
public static void main(String args[]){ 
    Scanner in = new Scanner(System.in); 
    int length = in.nextInt(); 
    //System.out.println(length); 
    int[] array = new int[length]; 
    for(int i=0; i<length; i++) 
     array[i] = in.nextInt();  



    System.out.println("Max = "+ longestConvex(array, length)); 
} 

public static int longestConvex(int[] array, int n){ 
    if(n<=2) 
     return n; 

    int max = 0; 
    int[][] B = new int[n][n]; 
    B[0][0] = 1; 

    for(int i=1; i<n; i++){ 
     for(int j=0; j<n; j++){ 
      B[i][j] = 2; 
      for(int k=0; k<j; k++){ 
       if(B[j][k]+ 1 >B[i][j] && ((array[i] - array[j]) > (array[j] - array[k]))) 
        B[i][j] = B[j][k] + 1; 
      } 
      max = Math.max(max, B[i][j]); 
     } 
    } 

    return max; 
} 
}