最长镜像子序列？

Question

我有一个最长的镜像子序列问题，指出

数字a1，...的序列。 。 。如果m为偶数且为，则am被称为镜像全部1≤i≤m，ai = −am−i + 1。例如，3，-4、4，-3是镜像序列。

我需要输出最大镜像子序列的长度。例如，在输入1、5 -1、3上，最长的镜像子序列为1 -1，其长度为2

我对此的第一个尝试是如下的O（n ^ 3）解决方案。

int s[] = {1,5,-1,3}; 
int n = 4; 
int dp[n][n]; 

// Considering all mirrored 
// substrings of length 2 
for (int i = 0; i < n - 1; i++) 
    if (s[i + 1] == -s[i]) 
        dp[i][i + 1] = 2; 

// Considering all other subsequences 
for (int l = 2; l < n; l++) 
{ 
    for (int i = 0, j = l; j < n; i++, j++) 
    { 
        if (s[j] == -s[i]) 
            dp[i][j] = 2 + dp[i + 1][j - 1]; 

        for (int k = i; k < j; k++) 
            dp[i][j] = max(dp[i][j], 
                        dp[i][k] + 
                    dp[k + 1][j]);       
    } 
} 

System.out.println(dp[0][n - 1]); 

}

我该如何优化O（n ^ 2）的解决方案？

Answer 1

您可以参考Geeks for Geeks网站上提供的解决方案来解决类似问题。https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/