CODEWITHSUNDEEP
c++algorithmdebuggingdynamic-programming
Nalin Bhardwaj
Nalin Bhardwaj

Reputation: 223

Zig-Zag sequence[Dynamic Programming] bugs

I currently learning DP and I was studying via the topsider tutorial, and was trying to solve the problem ZigZag sequence and understand and know that the solution would be very similar to computing the length go longest increasing subsequence. I programmed a simple c++ DP solution as follows:

#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())));
}

But the problem is that the code works fine for all other cases, except this one:

{ 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 }

My code prints the answer 35 while topsider believes its 36. I know Im making some kind of silly mistake in the program, but have been trying to find it since quite some time now, can someone else help me figure out the bug ?

Upvotes: 1

Views: 435

Answers (1)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I suspect the problem is that the first difference can be either positive or negative, but your code only supports one of these cases.

Maybe you should run this code twice, once with positive first, then the second time with negative first.

Upvotes: 3

Related Questions