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

Question

Может ли кто-нибудь помочь мне понять основную логику решения проблемы, упомянутой в 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; i<arr.length;i++)
        {
            maxLength=-100;
            for(int j=1;j<i && j+1<=arr.length; j++)
            {
                if(( arr[j]>arr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]<arr[j-1] && arr[j]<arr[j+1]))
                {
                    maxLength = Math.max(dpStore[j]+1, maxLength);
                }
            }
            dpStore[i]=maxLength;               
        }
    }
    max=-1000;
    for(int i=0;i<arr.length;i++)
    {
        max=Math.max(dpStore[i],max);
    }
    return max; 
}

Answer 1

def ZigZag (tup):

length = len(tup)
lst = []
lst.append(1)
lst.append(2)
if length > 2:
    for i in range(2,length):
        if (tup[i]-tup[i-1]) * (tup[i-1]-tup[i-2]) < 0:
            d = lst[i-1] + 1
        else:
            d = lst[i-1]
        lst.append(d)

return lst[length-1]