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

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

Вот о чем говорит ваша проблема:

Последовательность чисел называется зигзагообразной последовательностью, если различия между последовательными числами строго чередуются между положительными и отрицательными. Первое различие (если оно существует) может быть положительным или отрицательным. Последовательность с менее чем двумя элементами тривиально является зигзагообразной последовательностью.

Например, 1,7,4,9,2,5 - зигзагообразная последовательность, потому что различия (6, -3,5, -7,3) попеременно положительны и отрицательны. Напротив, 1,4,7,2,5 и 1,7,4,5,5 не являются зигзагообразными последовательностями: первое, потому что его первые две разницы положительны, а второе, потому что его последнее различие равно нулю.

Учитывая последовательность целых чисел, последовательность, возвращает длину самой длинной подпоследовательности последовательности, которая является зигзагообразной последовательностью. Подпоследовательность получается удалением некоторого количества элементов (возможно, нуля) из исходной последовательности, оставляя оставшиеся элементы в их первоначальном порядке.

Это полностью отличается от того, что вы описали в своем посте. Следующее решает актуальную проблему topcoder.

dp[i, 0] = maximum length subsequence ending at i such that the difference between the
           last two elements is positive
dp[i, 1] = same, but difference between the last two is negative

for i = 0 to n do     
   dp[i, 0] = dp[i, 1] = 1

   for j = 0 to to i - 1 do
    if a[i] - a[j] > 0
      dp[i, 0] = max(dp[j, 1] + 1, dp[i, 0])
    else if a[i] - a[j] < 0
      dp[i, 1] = max(dp[j, 0] + 1, dp[i, 1])

Пример:

i        = 0  1   2  3   4   5   6   7  8   9
a        = 1  17  5  10  13  15  10  5  16  8 
dp[i, 0] = 1  2   2  4   4   4   4   2  6   6    
dp[i, 1] = 1  1   3  3   3   3   5   5  3   7
           ^  ^   ^  ^
           |  |   |  -- gives us the sequence {1, 17, 5, 10}
           |  |   -- dp[2, 1] = dp[1, 0] + 1 because 5 - 17 < 0.
           |  ---- dp[1, 0] = max(dp[0, 1] + 1, 1) = 2 because 17 - 1 > 0
     1 element
   nothing to do
 the subsequence giving 7 is 1, 17, 5, 10, 5, 16, 8, hope I didn't make any careless
 mistakes in computing the other values)

Тогда просто возьмите максимум обоих dp массивов.

Answer 2

Это более простое решение

Пусть исходный массив A имеет длину n. Создайте другой массив B длиной n-1, состоящий только из 0 и 1. B [i] = 0, если a [i] -a [i + 1]> = 0, иначе B [i] = 1. Это можно сделать за O (n). Теперь у нас есть массив только 0 и 1, теперь проблема состоит в том, чтобы найти чередующиеся непрерывные 0 и 1. Непрерывный массив подмассива в B, равный 0, будет представлен любым одним из его элементов. Например: Если B = = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0], то мы можем уменьшить B до Br, который = [0,1,0 , 1,0,1,0] в O (n), на самом деле нам просто нужно найти размер Br, который можно сделать всего за одну итерацию. И именно мой друг является ответом на данную проблему. Таким образом, общая сложность составляет O (n) + O (n) = O (n). Другими словами: Оставь первый элемент. Затем найдите монотонно растущие или уменьшающиеся части последовательности и сохраните последний элемент из всех этих последовательностей.

ОБНОВЛЕНИЕ: вам нужно добавить один к ответу, выходящему из этого процесса, потому что вы учитываете зигзаги, а не длину списка. Остерегайтесь проблемы с забором: https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/

Answer 3

Есть и жадный подход.

Возьмите первый элемент. Затем найдите минимальный или максимальный элемент в непрерывной последовательности, включая первый элемент, и выберите его.

То есть, если последовательность равна 1, 5, 7, 9, 2,4, сначала выберите 1, а затем 9, поскольку 9 является максимумом в непрерывной последовательности 1, 5, 7, 9.

Продолжайте таким же образом и выберите 2 и 5. Используя тот же подход, подпоследовательность вычисляется для примера:

1, 17, 5, 10, 13, 15, 10, 5, 16, 8

- это: 1, 17, 5, 15, 5, 16, 8

Answer 4

На самом деле я думаю, что ответ с наивысшим баллом правильный (IVlad's). Но я уверен, что часть динамического программирования (внешний цикл) не необходима.

Используется жадный подход, и мы можем получить positive_end_seq[i] и negative_end_seq[i] с помощью операций:

    positive_end_seq[i] = negative_end_seq[i-1];
    negative_end_seq[i] = positive_end_seq[i-1];
    if (A[i-1] > A[i]) { // next element for positive_end_seq
       positive_end_seq[i] += 1; 
    }
    if (A[i-1] < A[i]) { // next element for negqtive_end_seq
       negative_end_seq[i] += 1;
    }
    // if (A[i-1] == A[i]) values don't change

positive_end_seq[0] = 1 и negative_end_seq[0] = 1, оба массива для всех i содержат длину самой длинной подпоследовательности с положением / отрицанием, заканчивающимся i -ым элементом. Нам не нужно смотреть на 0..i-2 элементов, и было бы неплохо доказать это.

Сложность времени составляет O(n)

Конечно, массив pos / neg теперь можно заменить счетчиками, вот код на Java

    public static int subZigZag(int[] arr) {
      int pos_count = 1;
      int neg_count = 1;
      for(int i = 1; i < arr.length; ++i) {
        if (arr[i-1] < arr[i]) {
          pos_count = neg_count + 1;
        }
        if (arr[i-1] > arr[i]) {
          neg_count = pos_count+1;
        }
      }
      return Math.max(pos_count, neg_count);
    } 

Answer 5

или вы можете использовать жадный алгоритм

public static int longestZigZag(int[] sequence) {
    if (sequence.length==1) return 1;
    if (sequence.length==2) return 2;
    int[] diff = new int[sequence.length-1];

    for (int i=1;i<sequence.length;i++){
        diff[i-1]=sequence[i]-sequence[i-1];
    }
    int prevsign=sign(diff[0]);
    int count=0;
    if (prevsign!=0)
        count=1;
    for (int i=1;i<diff.length;i++){
        int sign=sign(diff[i]);
        if (prevsign*sign==-1){
            prevsign=sign;
            count++;
        }
    }
    return count+1;
}

public static int sign(int a){
    if (a==0) return 0;
    return a/Math.abs(a);
}

Answer 6

int зигзаг (int [] a) {

List<Integer> list= new ArrayList<>();
int max = 0;
if(a.length==0 || a.length==1) return 0;
if(a.length==2) return 1;
for(int i=1;i<a.length-1;i++){

    if((a[i-1]<a[i] && a[i+1]<a[i]) || (a[i-1]>a[i] && a[i+1]>a[i])){
        if(list.isEmpty()){
           list.add(a[i-1]); 
        }
        list.add(a[i]);

    }else{
        list.add(a[i+1]); 
        max = Math.max(max,list.size());
        list.clear();
    }

}
return max;

}

Answer 7

Выберите локальные максимумы и локальные минимумы, очень просто.

vector<int> longest_oscilating_subsequence(const vector<int> seq) {
    vector<int> result; // the resulting subsequence 

    for (int i = 0; i < seq.size(); ++i) {
        if (i > 0 && seq[i] == seq[i - 1]) continue;

        // is this point a local extreme 
        bool local_max = true, local_min = true;
        if (i > 0) {
            local_max = local_max && (seq[i] >= seq[i - 1]);
            local_min = local_min && (seq[i] <= seq[i - 1]);
        }
        if (i < seq.size() - 1) {
            local_max = local_max && (seq[i] >= seq[i + 1]);
            local_min = local_min && (seq[i] <= seq[i + 1]);
        }

        // potentially add it to the sequence 
        if (local_max || local_min) result.push_back(seq[i]);
    }

    return result; 
}

Answer 8

Вот как это получилось за O (n)

public static int longestZigZag(int[] sequence) {
    if (sequence == null) {
        return 0;
    }

    int len  = sequence.length;
    if (len <= 2) {
        return len;
    }
    int minima = sequence[0];
    int maxima = sequence[0];
    int maximalen = 1;
    int minimalen = 1;

    for (int i = 1; i < len; i++) {
        if (sequence[i] < maxima) {
            if (minimalen < maximalen + 1) {
                minimalen = maximalen + 1;
                minima = sequence[i];
            } else if (minimalen == maximalen + 1 && sequence[i] < minima) {
                minima = sequence[i];
            }
        }
        if (sequence[i] > minima) {
            if (maximalen < minimalen + 1) {
                maximalen = minimalen + 1;
                maxima = sequence[i];
            } else if (maximalen == minimalen + 1 && sequence[i] > maxima) {
                maxima = sequence[i];
            }
        }
    }

    return Math.max(maximalen, minimalen);
}

Answer 9

Это мое простое жадное воплощение.

Как и другие, о которых упоминалось ранее, вам просто нужно взглянуть на загоны трех последних пунктов.

def zigzag(xs):
    res = xs[:2]
    for x in xs[2:]:
        if cmp(res[-1], x) == cmp(res[-1], res[-2]):
            res.append(x)
        else:
            res[-1] = x
    return res

Answer 10

public static int longestZigZag(int[] sequence) {
    int max_seq = 0;

    if (sequence.length == 1) {
        return 1;
    }

    if (sequence.length == 1) {
        return 2;
    }

    int dp[] = new int[sequence.length];

    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i < sequence.length; i++) {
        for (int j = i - 1; j > 0; j--) {
            if (((sequence[i] > sequence[j] &&
                sequence[j] < sequence[j - 1]) || 
                (sequence[i] < sequence[j] &&
                sequence[j] > sequence[j - 1])) &&
                dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;

                if (dp[i] > max_seq) {
                    max_seq = dp[i];
                }
            } 
        }
    }

    return max_seq;
}