Zig-Zag 序列 [动态编程] 错误

Question

我目前正在学习 DP，我正在通过 topsider 教程学习，并试图解决问题 ZigZag sequence 并且理解并知道解决方案与计算长度 go 最长递增子序列非常相似。我编写了一个简单的 C++ DP 解决方案，如下所示：

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
    int n = 50;
    int numbers[] =         
{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 };
    vector<int> length(n, 1);
    for(int i = 1;i < n;i++)
    {
        for(int j = (i - 1);j >= 0;j--)
        {
            if(length[j] + 1 > length[i])
            {
                if(length[j] % 2 == 0)
                {
                    if(numbers[i] - numbers[j] < 0)
                    {
                        length[i] = length[j] + 1;
                    }
                }
                else
                {
                    if(numbers[i] - numbers[j] > 0)
                    {
                        length[i] = length[j] + 1;
                    }
                }
            }
        }
    }
    printf("%d\n", *(max_element(length.begin(), length.end())));
}

但问题是代码在所有其他情况下都能正常工作，除了这个：

{ 374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
249, 22, 176, 279, 23, 22, 617, 462, 459, 244 }

我的代码打印答案 35，而 topsider 相信它 36。我知道我在程序中犯了一些愚蠢的错误，但是很长一段时间以来一直在努力寻找它，其他人可以帮我找出错误吗？

Answer 1

我怀疑问题在于第一个差异可以是正数也可以是负数，但您的代码只支持其中一种情况。

也许你应该运行这段代码两次，第一次是正数，第二次是负数。

Zig-Zag 序列 [动态编程] 错误

Zig-Zag sequence[Dynamic Programming] bugs

c++

algorithm

debugging

dynamic-programming