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

Question

Можно ли решить эту проблему, используя только один массив dp? Это проблема зигзага от topcoder (http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493) Последовательность чисел называется последовательностью зигзага, если различия между последовательными числами строго чередуются между положительными и отрицательными. Первое различие (если оно существует) может быть как положительным, так и отрицательным. Последовательность с менее чем двумя элементами тривиально представляет собой зигзагообразную последовательность.

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

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

Answer 1

Для справки: DP с двумя массивами использует массив A [1..n], где A [i] - максимальная длина зигзагообразной последовательности, заканчивающейся зиг на элементе i, и массив B [ 1..n], где B [i] - максимальная длина зигзагообразной последовательности, заканчивающаяся zag на элементе i. Для i от 1 до n этот DP использует предыдущие записи массива A для вычисления B [i] и предыдущих записей массива B для вычисления A [i]. За счет дополнительного цикла можно было бы воссоздать записи B по требованию и, таким образом, использовать только массив A. Я не уверен, что это решает вашу проблему.

(Кроме того, поскольку входные массивы настолько коротки, есть любое количество трюков кодирования не стоит упомянуть.)

Answer 2

Вот попытка, я возвращаю индексы, откуда у вас есть зигзаг. На вашем втором входе (1,4,7,2,5) он возвращает индексы 5 и 4, поскольку это зигзаг от 4,7,2,5.

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

public class LongestZigZag 
    { 
     private readonly int[] _input; 

     public LongestZigZag(int[] input) 
     { 
      _input = input; 
     } 

     public Tuple<int,int> Sequence() 
     { 
      var indices = new Tuple<int, int>(int.MinValue, int.MinValue); 

      if (_input.Length <= 2) return indices; 

      for (int i = 2; i < _input.Length; i++) 
      { 
       var firstDiff = _input[i - 1] - _input[i - 2]; 
       var secondDiff = _input[i] - _input[i - 1]; 

       if ((firstDiff > 0 && secondDiff < 0) || (firstDiff < 0 && secondDiff > 0)) 
       { 
        var index1 = indices.Item1; 
        if (index1 == int.MinValue) 
        { 
         index1 = i - 2; 
        } 

        indices = new Tuple<int, int>(index1, i); 
       } 
       else 
       { 
        indices = new Tuple<int, int>(int.MinValue, int.MinValue); 
       } 
      } 

      return indices; 
     } 
    } 

Answer 3

Динамическое программирование занимает O (п) время, чтобы запустить программу. Я разработал код, который имеет сложность линейного времени O (n). С одним шагом в массиве он дает длину самой большой возможной последовательности. Я тестировал для многих тестовых случаев, предоставленных различными сайтами для проблемы, и получил положительные результаты.

Вот моя реализация C кода:

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
int i,j; 
int n; 
int count=0; 
int flag=0; 
scanf(" %d",&n); 
int *a; 
a = (int*)malloc(n*sizeof(a)); 

for(i=0;i<n;i++) 
{ 
    scanf(" %d",&a[i]); //1,7,5,10,13,15,10,5,16,8 
} 
i=0; 
if(a[0] < a[1]) 
{ 
    count++; 
    while(a[i] <= a[i+1] && i<n-1) 
    i++; 

    if(i==n-1 && a[i-1]<a[i]) 
    { 
     count++; 
     i++; 
    }  
} 
    while(i<n-1) 
    { count++; 
     while(a[i] >= a[i+1] && i<n-1) 
     { 
     i++; 
     } 
     if(i==n-1 && a[i-1]>a[i]) 
     { 
      count++; 
      break; 
     }  
     if(i<n-1) 
     count++; 
     while(a[i] <= a[i+1] && i<n-1) 
     { 
      i++; 
     } 
     if(i==n-1 && a[i-1]<a[i]) 
     { 
      count++; 
      break; 
     }   
    }  

printf("%d",count); 
return 0; 
}  

Answer 4

public class ZigZag 
{ 

    public void maxZigZag(int[] zigzag) 
    { 
    int sign[]=new int[zigzag.length]; 
    int p=0; 
    int max=1; 
     for(int j=0;j<zigzag.length-1;j++) 
     { 
      if(zigzag[j+1]-zigzag[j] > 0) 
       sign[p++]=1; 
      else if(zigzag[j+1]-zigzag[j] < 0) 
       sign[p++]=-1; 
     } 
     /*for(int s:sign) 
     { 
      System.out.print(s+","); 
     }*/ 
     System.out.println(); 
     for(int k=0;k<p;k++) 
     { 
      if(sign[k]==sign[k+1]) 
      { 
       sign[k]=0; 

      } 
     } 
     /*for(int s:sign) 
     { 
      System.out.print(s+","); 
     }*/ 
     System.out.println(); 
     for(int s=0;s<p;s++) 
     { 
      if(sign[s]!=0) 
      { 
       max++; 
       /*System.out.print(sign[s]+",");*/ 
      } 

     } 

     System.out.println("max length zigzag:"+max); 
    } 

    public static void main(String args[]) 
    { 
    ZigZag z=new ZigZag(); 
    int zigzag[]={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}; 
    z.maxZigZag(zigzag); 
    } 
} 

Answer 5

Каждый (к моему знанию по данной теме, поэтому не принимайте это как должное) решение, которое вы работаете с динамическим программированием, приходит вплоть до представления «пространства решений» (что означает любое возможное решение, которое является правильным, а не обязательно оптимальным) с DAG (Направленный ациклический график).

Например, если вы ищете самый длинный роста subseqence, то пространство решение может быть представлено в виде следующей DAG:

• Узлы помечены номерами последовательности
• Край e(u, v) между двумя узлами указывает на то, что valueOf(u) < valueOf(v) (где valueOf(x) это значение, связанное с узлом x)

в динамическое программирование, поиск оптимального решения проблемы - это то же самое, что и правильное пересечение этого графика. Информация, предоставленная этим графиком, в некотором смысле представлена ​​этим массивом DP.

В этом случае мы имеем две операции упорядочения. Если бы мы представили оба из них на одном из таких графиков, этот график не был бы ацикличен - нам потребуются как минимум два графика (один из которых представляет отношение <, а один для >).

Если для топологического упорядочения требуются два DAG, для решения потребуется два массива DP или какой-либо умный способ указать, какое из краев в вашей DAG соответствует какой операции упорядочения (что, на мой взгляд, не требует усложнения проблемы).

Следовательно нет, вы не можете сделать это только с одним массивом DP. Вам потребуется не менее двух. По крайней мере, если вам нужно простое решение, к которому обращаются исключительно с помощью динамического программирования.

---

Рекурсивный вызов этой проблемы должно выглядеть примерно так (направления отношений может быть неправильно, я не проверял):

S - given sequence (array of integers) 
P(i), Q(i) - length of the longest zigzag subsequence on elements S[0 -> i] inclusive (the longest sequence that is correct, where S[i] is the last element) 

P(i) = {if i == 0 then 1 
     {max(Q(j) + 1 if A[i] < A[j] for every 0 <= j < i) 


Q(i) = {if i == 0 then 0 #yields 0 because we are pedantic about "is zig the first relation, or is it zag?". If we aren't, then this can be a 1. 
     {max(P(j) + 1 if A[i] > A[j] for every 0 <= j < i) 

Это должно быть O (п) с правой memoization (два массива DP). Эти вызовы возвращают длину решения - фактический результат можно найти, сохранив «родительский указатель» всякий раз, когда будет найдено максимальное значение, а затем перемещение назад по этим указателям.