我的解決方案有什麼問題 - SPOJ - ALTSEQ？

Question

我需要做什麼：我需要解決[ this ] SPOJ上的問題。給定一個由N個整數a1，a2，a3，...，aN組成的數組a1，我必須找到該數組的最長交替子序列的長度。
的交替序列B1，B2 ... BK中，k> = 1是具有2種以下性質的序列：

1. | B1 | < | b2 | < | b3 | < ..... < | bk |
2. 符號在相鄰元素之間交替，即如果b1> 0，則b2 < 0，b3> 0等等。或者，如果b1 < 0，則b2> 0，b3 < 0等等。

我的方法：
問題是最長遞增子（LIS）問題的變化。這裏是我的記憶化遞推的解決方案：

#include <cstdio> 
using namespace std; 

long *a; 
int *dp; 

int solve(int); 
int main() 
{ 
    int n; 
    scanf("%d", &n); 
    a = new long[n]; 
    dp = new int[n]{}; 
    for (int i = 0; i < n; i++) scanf("%ld", a+i); 
    printf("%d", solve(n-1)); 
} 

int solve(int n) 
{ 
    if (dp[n]) return dp[n]; 
    int &m = dp[n] = 1, k; 
    for(int j = 0; j < n; j++) 
     if (((a[n] < 0 && a[j] > 0 && -a[n] > a[j]) || (a[n] > 0 && a[j] < 0 && a[n] > -a[j]))) 
      if ((k = 1 + solve(j)) > m) m = k; 
    return m; 
} 

我的問題：該解決方案使法官系統錯誤答案所以一定有什麼不對的地方。我需要幫助來弄清楚這個解決方案有什麼問題，因爲我不能自己做。

Answer 1

後來我發現解決方案（i）正在計算dp [i]，它是以第i個元素結尾的LIS。因此，整個dp數組的最大值是我之前打印的正確答案，而不是dp [n-1]。

此外，遞歸解決方案可以轉換爲自下而上的效率。此外，在自下而上的情況下，所涉及的兩個循環中的外部循環可以與輸入讀取循環組合，並且最大dp [i]可以在外部循環內保持跟蹤，以避免另一個循環找到最大值。這應該會導致更快的解決方案。

#include <cstdio> 
using namespace std; 

int main() 
{ 
    int n, k, m = 0; 
    scanf("%d", &n); 
    long *a = new long[n]; 
    int *dp = new int[n]; 
    for (int i = 0; i < n; i++) { 
     scanf("%ld", a+i); 
     dp[i] = 1; 
     for (int j = 0; j < i; j++) 
      if (((a[i] < 0 && a[j] > 0 && -a[i] > a[j]) || (a[i] > 0 && a[j] < 0 && a[i] > -a[j])) && (k = 1 + dp[j]) > dp[i]) dp[i] = k; 
     if (dp[i] > m) m = dp[i]; 
    } 
    printf("%d\n", m); 
}