私の解決策は何ですか？SPOJ - ALTSEQ？

Question

私がする必要があるもの：私は解決する必要があります[ this ] SPOJに問題があります。

N個の整数a1、a2、a3、... aNの配列aが与えられていれば、配列の最長交互配列の長さを求めなければならない。
交互配列B1、B2 ... BK、K> = 1は2つの以下の特性を有する配列である

1. | B1 | < | b2 | < | b3 | < ..... < | bk |
2. 記号は隣接要素間で交互に表示されます。つまり、b1> 0の場合はb2 <、b3> 0の場合などです。あるいは、b1 <が0の場合、b2> 0、b3 <などとなります。

私のアプローチ：
問題が最長増加部分列（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）がi番目の要素で終わるLISであるdp [i]を計算していることが後で私に起こりました。したがって、dp配列全体の最大値は、私が以前に印刷していた正解ではありません（dp [n-1]）。

また、再帰的ソリューションは効率のためにボトムアップに変換できます。さらに、ボトムアップでは、関連する2つのループの外側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); 
}