Tranche la plus longue avec des nombres entiers positifs et négatifs alternés

Question

Pour un tableau avec des valeurs positives et négatives, renvoyer la taille de coupe alternée maximale continue, deux éléments sont alternés s'ils ont des signes différents, zéro est considéré comme négatif et positif.

Exemple a = [1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3] Compte tenu de retour 7 (la séquence [1, 0, 2, -5, 3, -1, 1] a au maximum la taille de la tranche alternatif)

Le temps d'exécution attendu est O(n).

J'ai essayé de résoudre le problème comme sequnce avec la somme max:

def sol(a): 
n = len(a) 
l = 0 
left = 0 
right = 0 
tot = 1 
for i in range(1,n): 
    if a[i]*a[i-1] > 0: 
     l = i + 1 
    else: 
     if i-l > right-left: 
      right = i 
      left = l 
      tot = max(tot,right-left+1) 
return tot 

Je suppose que cela est une mauvaise approche, mais ne peut pas penser à d'autres

Answer 1

approche Vous est bon, juste initialize série démarre correctement et supprimer des actions excessives:

def sol(a): 
    l = 0 
    tot = 1 
    for i in range(1, len(a)): 
     if a[i]*a[i-1] > 0: #series violation 
      tot = max(tot, i - l) 
      l = i 
    return tot 

Answer 2

Je suppose que je din't lu le problème correctement. L'algorithme ci-dessous est valable pour les sous-séquences non continues.

---

Maintenir deux variables maxPositive et maxNegetive qui contient la longueur de la plus grande tranche se terminant par un nombre entier positif et négatif pour tout entier input[i].

Psuedo-Code

maxPositive = 0, maxNegetive = 0 
answer = 1 

for i: 1 to n 
    if(input[i] > 0) 
    maxPositive = max(maxPositive , maxNegetive + 1) 
    else if(input[i] < 0) 
    maxNegetive = max(maxNegetive , maxPositive + 1) 
    else 
    TempNegative = maxPositive + 1 
    TempPositive = maxNegetive + 1 
    maxPositive = max(maxPositive, TempPositive) 
    maxNegetive = max(maxNegetive , TempNegative) 

    int currentMax = max(maxPositive, maxNegative) 

    if(currentMax > answer) 
    answer = currentMax 

return answer   

Answer 3

Pour savoir si deux valeurs sont des symboles en alternance (y compris zéro), vous devez vérifier si la différence entre ces deux valeurs est supérieure ou égale à leurs valeurs absoulte. En d'autres termes, essayez ceci:

 

    def sol(a): 
     m = 0 
     for i in range(len(a)): 
      j = i+1 
      while j<len(a): 
       r = abs(a[j-1]-a[j]) 
       if r<abs(a[j-1]) or r<abs(a[j]): break 
       j+=1 
      if j-i>m: m=j-i 
     return m 

Answer 4

Essayez this-

LOGIC- Le maintien d'un départ pour notre itération, lorsque notre itération se brise, nous comparons simplement notre longueur maximale actuelle à la longueur maximale globale.

NOTE - Avant la fin de l'itération, nous devons vérifier une dernière fois.

#include <bits/stdc++.h> 
    using namespace std; 


    int main(){ 
     int n; 
     cin>>n; 
     vector<int> v(n); 
     for(int i=0;i<n;i++){ 
      int c;cin>>c; 
      v[i]=c; 
     } 
     int start=0;int maxlength=INT_MIN; 
     for(int i=1;i<n;i++){ 
      if((v[i]>=0&&v[i-1]<=0)||(v[i]<=0&&v[i-1]>=0)){ 
       if(i==n-1){ 
        int length=i-start+1; 
        if(maxlength<length) maxlength=length; 
       } 
      }else{// 
       int length=i-start; 
       if(maxlength<length) maxlength=length; 
       start=i; 
      } 
     } 
     //cout<<start; 
     cout<<maxlength; 
     return 0; 
    }