正と負の整数を交互に持つ最長スライス

Question

正と負の値を持つ配列が与えられた場合、交互に繰り返されるスライスの最大サイズが返され、2つの要素が異なる符号を持つ場合は交互になり、ゼロは負と正の両方として扱われます。

例 a = [1, -5, 23, 0, 1, 1, 0, 2, -5, 3, -1, 1, 2, 3]はリターン7（配列[1, 0, 2, -5, 3, -1, 1]有する最大交流スライスサイズ）指定

予想ランタイムがO(n)あります。

私は最大の和とsequnceのような問題を解決しようとした：

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 

私は私が読んdin't推測、これは間違ったアプローチであると思いますが、他の

Answer 1

あなたのアプローチは良いですが、ちょうどシリーズが正常に起動し初期化し、削除し、過剰なアクション：

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

を考えることはできません問題は正しく発生します。以下のアルゴリズムは、連続シーケンスではない部分シーケンスに対して良好に保持される。

---

任意input[i]ための正の整数と負の整数で終わる最大スライスの長さを保持する二つの変数maxPositiveとmaxNegetiveを維持します。

擬コード

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

二つの値を使用して、これらの値の差が大きいか、またはそれらabsoulte値より等しいかどうかをテストしなければならない（ゼロを含む）のシンボルを交互にしているかどうかを知ります。言い換えれば、これを試してみてください。

 

    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

はthis-

いるロジックは、の開始を維持してください、私たち私たちの反復が壊れたとき、現在の最大長をグローバル最大長と比較するだけです。

注 - 反復が終了する前に、最後に確認する必要があります。

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