交替正整數和負整數的最長切片

Question

給定具有正值和負值的數組，返回最大連續切片大小，如果兩個元素具有不同的符號，則返回兩個元素交替，零被視爲負值和正值。

例 鑑於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 

我想這是一個錯誤的做法，但想不出其他

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

我想我din't閱讀問題正確。以下算法適用於子序列而非連續序列。

---

維持兩個變量maxPositive和maxNegetive這保持了與正整數和負整數任何input[i]結束最大片的長度。

僞代碼

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

嘗試這個 -

邏輯值維持一開始我們迭代，當我們的迭代中斷時，我們只比較我們當前的最大長度和全局最大長度。

注 - 在迭代終止前，我們必須檢查最後一次。

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