Динамическое программирование: найдите самую длинную подпоследовательность, которая является зигзагообразной

Может ли кто-нибудь помочь мне понять основную логику решения проблемы, упомянутой на http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

Зигзагообразная последовательность - это та, которая попеременно увеличивается и уменьшается. Итак, 1 3 2 - зигзаг, а 1 2 3 - нет. Любая последовательность из одного или двух элементов - зигзаг. Нам нужно найти самую длинную зигзагообразную подпоследовательность в заданной последовательности. Подпоследовательность означает, что элементы не обязательно должны быть смежными, как в задаче о самой длинной возрастающей подпоследовательности. Итак, 1 3 5 4 2 может иметь 1 5 4 в виде зигзагообразной подпоследовательности. Нас интересует самый длинный.

Я понимаю, что это проблема динамического программирования, и она очень похожа на Как определить самую длинную возрастающую подпоследовательность с помощью динамического программирования? .

Я думаю, что любая для решения потребуется внешний цикл, который выполняет итерацию по последовательностям разной длины, а внутренний цикл должен будет перебирать все последовательности.

Мы будем хранить самую длинную зигзагообразную последовательность, заканчивающуюся индексом i, в другом массиве, скажем, dpStore с индексом i . Таким образом, промежуточные результаты сохраняются, и их можно использовать повторно. Эта часть является общей для всех задач динамического программирования. Позже мы находим глобальный максимум и возвращаем его.

Мое решение определенно неверное, вставляю сюда, чтобы показать, что я сделал до сих пор. Я хочу знать, где я ошибся.

    private int isZigzag(int[] arr)
{
    int max=0;
    int maxLength=-100;
    int[] dpStore = new int[arr.length];

    dpStore[0]=1;

    if(arr.length==1)
    {
        return 1;
    }
    else if(arr.length==2)
    {
        return 2;
    }
    else 
    {           
        for(int i=3; iarr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]