具有交替的正整数和负整数的最长切片

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

我尝试用最大总和解决问题，如序列：

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
    tot = max(tot, len(a) - l) #check the last good series 
    return tot 

Answer 2

要知道两个值是否为交替符号（包括零），您必须测试这些值之间的差异是否大于或等于其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 3

试试这个-

逻辑 - 维持迭代的开始，当我们的迭代中断时，我们只是将当前的最大长度与全局最大长度进行比较。

注 - 在迭代终止之前，我们必须检查最后一次。

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

Answer 4

我想我没有正确地阅读这个问题。以下算法适用于不是连续序列的子序列。

---

保持两个变量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 5

请在下面找到此问题的java代码： 方法是在满足条件中给出的某些标准时保持递增结束指数。 当没有if条件为真时，我们从while循环中断并计算更新到达该点所达到的最大长度。

public static int solution(int[] A) {

    int max = 1, start = 0, end = 0;
    int arrLen = A.length;

    for(int i = 0; i < arrLen-1 ; ++i){
        start = i;
        end = start;
        while( end+1 < arrLen ){
            if( A[end] * A[end+1] < 0 ){
                end++;
            }else if((end == 0) && (A[end] * A[end+1]) == 0){
                end++;
            }else if((A[end] == 0) && (A[end-1] * A[end+1] >= 0)){
                end++;
            }else if(A[end+1] == 0){
                end++;
            }else if((end+1 == arrLen-1) && (A[end] * A[end+1] == 0)){
                end++;
            }else{
                break;
            }
        }
        if(max < end-start+1){
            max = end-start+1;
        }   
    }   
    return max;
}

Answer 6

1. 对于匹配切片的序列，我们必须注意下一个正确的答案，即如果我们以arr [p] <= 0开始，那么下一个期望值应该是arr [p]> = 0或反之。
2. 要监视下一个目标输入，我们使用目标（如果下一个期望值<= 0，目标将设置为0，如果下一个期望值> = 0，目标将设置为1，如下所示。
3. 当找到正确的目标时，sum加1
4. max通过与sum进行比较来保持我们到目前为止遇到的最大切片。

   public static int getMaxSlice(int[] arr) {
   int max=1;int sum = 1;
   int target;//monitors the next expected value (0 for <=0 and 1 for>=0)
   if (arr.length >= 1) {
       if (arr[0] <= 0) {
           target = 0;
       } else {
           target = 1;
       }
       for (int i = 1; i < arr.length; i++) {
           if (target == 0) {
               if (arr[i] >= 0) {
                   target = 1;
                   sum += 1;
                   if(sum>max){
                       max=sum;
                   }
               }else{
                   target = 0;
                   sum=1;
               }
           }else{
               if (arr[i] <= 0) {
                   target = 0;
                   sum += 1;
                   if(sum>max){
                       max=sum;
                   }
               }else{
                   target = 1;
                   sum=1;
               }
           }
       }
   }
   return max;

   }