algorithm - rompehielos - Programación dinámica: encuentra la subsecuencia más larga que es zig zag

dinamicas rompehielos divertidas

Question

¿Alguien puede ayudarme, por favor, a entender la lógica central detrás de la solución a un problema mencionado en http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

Una secuencia de zig zag es aquella que aumenta y disminuye alternativamente. Entonces, 1 3 2 es zig zag, pero 1 2 3 no lo es. Cualquier secuencia de uno o dos elementos es zig zag. Necesitamos encontrar la subsecuencia en zigzag más larga en una secuencia dada. Subsecuencia significa que no es necesario que los elementos sean contiguos, como en el problema de subsecuencias en aumento más largo. Entonces, 1 3 5 4 2 podría tener 1 5 4 como una subsecuencia en zig zag. Estamos interesados ​​en el más largo.

Entiendo que este es un problema de programación dinámica y es muy similar a ¿Cómo determinar la subsecuencia con el aumento más largo utilizando programación dinámica? .

Creo que cualquier solución necesitará un bucle externo que itere sobre secuencias de diferentes longitudes, y el bucle interno tendrá que iterar sobre todas las secuencias.

Almacenaremos la secuencia de zigzag más larga que termina en el índice i en otra matriz, digamos dpStore en el índice i. Por lo tanto, los resultados intermedios se almacenan, y luego se pueden reutilizar. Esta parte es común a todos los problemas de programación dinámica. Más tarde encontramos el máximo global y lo devolvemos.

Mi solución es definitivamente incorrecta, pegar aquí para mostrar lo que he hecho hasta ahora. Quiero saber dónde me equivoqué.

    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

Así es como lo hizo en 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 2

Elija máximos locales y mínimos locales, muy simple.

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 3

En realidad creo que la respuesta con la puntuación más alta es correcta (IVlad). Pero estoy bastante seguro de que la parte de programación dinámica (bucle externo) no es necesaria.

Se utiliza un enfoque codicioso y podemos obtener positive_end_seq[i] y negative_end_seq[i] por operaciones:

    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 y negative_end_seq[0] = 1 , ambas matrices para todos los i contienen la longitud de la subsecuencia más larga con pos / neg que termina en el elemento i -th. No tenemos que ver los elementos 0..i-2 , y sería bueno demostrarlo.

La complejidad del tiempo es O(n)

Por supuesto, la matriz pos / neg puede ser reemplazada por contadores ahora, aquí está el código en 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 4

Esta es mi opinión sobre una implementación codiciosa simple.

Como otros han mencionado anteriormente, simplemente debes mirar la zag''ing de los tres últimos puntos.

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 5

Esta es una solución más simple.

Deje que la matriz original A sea de longitud n. Construye otra matriz B de longitud n-1 de solo 0s y 1s. B [i] = 0 si a [i] -a [i + 1]> = 0 sino B [i] = 1. Esto se puede hacer en O (n). Ahora tenemos una serie de solo 0s y 1, ahora el problema es encontrar alternando 0s y 1s continuos. Una matriz de sub array continua en B de 0s será representada por cualquiera de sus elementos. Por ejemplo: si B es = [0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0] entonces podemos reducir B a Br, que = [0, 1,0,1,0,1,0] en O (n), de hecho, solo necesitamos encontrar el tamaño de Br que se puede hacer mediante una sola iteración. Y que mi amigo es la respuesta al problema dado. Entonces, la complejidad total es O (n) + O (n) = O (n). En otras palabras: mantener el primer elemento. Luego encuentre las partes monótonas que aumentan o disminuyen la secuencia y mantenga el último elemento de todas estas secuencias.

ACTUALIZACIÓN: debe agregar una a la respuesta que sale de este proceso, porque está contando los zigzags, no la longitud de la lista. Tenga cuidado con el problema de la publicación de vallas: https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/

Answer 6

Esto es lo que dice el problema con el que te vinculaste:

Una secuencia de números se denomina secuencia en zig-zag si las diferencias entre los números sucesivos se alternan estrictamente entre positivo y negativo. La primera diferencia (si existe) puede ser positiva o negativa. Una secuencia con menos de dos elementos es trivialmente una secuencia en zigzag.

Por ejemplo, 1,7,4,9,2,5 es una secuencia en zig-zag porque las diferencias (6, -3,5, -7,3) son alternativamente positivas y negativas. En contraste, 1,4,7,2,5 y 1,7,4,5,5 no son secuencias en zig-zag, la primera porque sus dos primeras diferencias son positivas y la segunda porque su última diferencia es cero.

Dada una secuencia de enteros, secuencia, devuelve la longitud de la subsecuencia más larga de secuencia que es una secuencia en zig-zag. Se obtiene una subsecuencia al eliminar algunos elementos (posiblemente cero) de la secuencia original, dejando los elementos restantes en su orden original.

Esto es completamente diferente de lo que describiste en tu publicación. Lo siguiente resuelve el problema real del codificador superior.

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])

Ejemplo:

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)

Entonces simplemente tome el máximo de ambas matrices dp .

Answer 7

Hay un enfoque codicioso también.

Toma el primer elemento. Luego, averigüe el elemento mínimo o máximo en la secuencia contigua que incluye el primer elemento y selecciónelo.

Es decir, si la secuencia es 1, 5, 7, 9, 2,4 , primero seleccione 1 y luego 9 porque 9 es el máximo en la secuencia contigua 1, 5, 7, 9 .

Proceda de la misma manera y seleccione 2 y 5. Usando el mismo enfoque, la subsecuencia calculada para el ejemplo:

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

es: 1, 17, 5, 15, 5, 16, 8

Answer 8

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]

Answer 9

int zigzag (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 10

o puedes usar algoritmo codicioso

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 11

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