La programmation dynamique: Trouver la plus longue sous-suite qui est en zig zag

C'est ce que le problème est lié à dit:

Une séquence de nombres est appelé un zigzag de la séquence si les différences entre les nombres strictement alterner entre le positif et le négatif. La première différence (si il existe) peut être positif ou négatif. Une séquence de moins de deux éléments est trivialement un zigzag de la séquence.

Par exemple, 1,7,4,9,2,5 est un zigzag de la séquence, car les différences (6,-3,5,-7,3) sont alternativement positifs et négatifs. En revanche, 1,4,7,2,5 et 1,7,4,5,5 ne sont pas en zigzag séquences, la première à cause de ses deux premières différences sont positives et le second en raison de sa dernière différence est égale à zéro.

Donné une séquence de nombres entiers, de séquence, de retour de la longueur de la plus longue sous-suite de la séquence qui est un zigzag de la séquence. Une sous-suite est obtenue par la suppression d'un certain nombre d'éléments (éventuellement zéro) à partir de la séquence d'origine, en laissant le reste des éléments dans leur ordre d'origine.

C'est complètement différent de ce que vous avez décrit dans votre post. Le suivant résout le réel topcoder problème.

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

Exemple:

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)

Puis il suffit de prendre le max de deux dp tableaux.

OriginalL'auteur IVlad

Il y a une approche gourmande aussi.

Prendre le premier élément. Puis de trouver le minimum ou le maximum de l'élément dans la séquence contiguë, y compris le premier élément et sélectionnez-la.

Qui est si la séquence est 1, 5, 7, 9, 2,4, sélectionnez d'abord 1, puis 9 car 9 est le maximum dans la séquence contiguë 1, 5, 7, 9.

Procéder de la même manière et sélectionnez 2 et 5.
En utilisant la même approche, la sous-suite calculé pour l'exemple:

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

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

OriginalL'auteur user434345

En fait, je pense que répondre avec le plus haut score est correct (IVlad). Mais je suis assez sûr que la dynamique de la partie programmation (boucle externe) est pas nécessaire.

Une approche gourmande est utilisé et on peut obtenir positive_end_seq[i] et negative_end_seq[i] par des opérations:

    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 et negative_end_seq[0] = 1, les deux tableaux pour tous les is'contient la longueur de la plus longue sous-suite avec pos/nég se terminant en i-ième élément. Nous n'avons pas à regarder 0..i-2 éléments, et il serait bien de prouver que.

Complexité temporelle est O(n)

Bien sûr, pos/neg tableau peuvent être remplacés par des compteurs maintenant, voici le code 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);
    } 

OriginalL'auteur The_Ham

C'est mon point de vue sur un simple avide de mise en œuvre.

Comme d'autres l'ont déjà mentionné, il vous suffit de regarder les zag avec les trois derniers points.

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

OriginalL'auteur Thomas Ahle

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;

}

OriginalL'auteur jchopra

De sélection locale de maxima et de minima locaux, très 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; 
}

OriginalL'auteur Lukas Mach