Längste Schicht mit abwechselnd positiven und negativen ganzen Zahlen

Question

Gegeben eine Matrix mit positiven und negativen Werten, die maximale kontinuierliche alternierende Schichtgröße zurückgibt, zwei Elemente wechseln sich ab, wenn sie unterschiedliche Vorzeichen haben, Null wird sowohl als negativ als auch als positiv behandelt.

Beispiel Gegeben a = [1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3] return 7 (die Reihenfolge hat [1, 0, 2, -5, 3, -1, 1] maximale Wechselscheibengröße)

Die erwartete Laufzeit ist O(n).

Ich habe versucht, das Problem wie sequnce mit max Summe zu lösen:

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 

Ich denke, dies ist ein falscher Ansatz, aber denken kann, nicht von anderen

Answer 1

Sie Ansatz gut, nur Serie richtig initialisiert werden beginnen, und entfernen Sie übermäßige Aktionen:

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

Ich glaube, ich das gelesen din't Problem richtig. Der folgende Algorithmus gilt für Subsequenzen nicht nicht kontinuierliche Sequenz.

---

zwei Variablen Pflegen maxPositive und maxNegetive, die die Länge des größten slice endend mit einer positiven ganzen Zahl und negative ganze Zahl für jede input[i] hält.

Psuedo-Kodex

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

Um zu wissen, ob zwei Werte Symbole werden abwechselnd (einschließlich Null) Sie testen, wenn die Differenz zwischen diesen Werten größer oder gleich als ihre absoulte Werte. Mit anderen Worten, versuchen Sie dies:

 

    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

Versuchen this-

Logik- Aufrechterhaltung eines Start für unsere Iteration, wenn unsere Iteration bricht, vergleichen wir nur unsere aktuelle maximale Länge mit der globalen maximalen Länge.

HINWEIS - Bevor die Iteration beendet wird, müssen wir ein letztes Mal prüfen.

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