乘积为正数的最长连续子数组

#include <iostream>
using namespace std;

int main() {
    int n, tmp, res = 0;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; ++i) cin >> arr[i];
    // 时间复杂度O(N)，空间复杂度O(1)
    int positive = 0, negative = 0;  // 最长正数子数组，最长负数子数组
    for (int i = 0; i < n; ++i) {
        if (arr[i] > 0) {
            ++positive;
            negative = negative == 0 ? 0 : negative + 1;
        } else if (arr[i] < 0) {
            tmp = negative;
            negative = positive + 1;
            positive = tmp == 0 ? 0 : tmp + 1;
        } else {
            positive = 0;
            negative = 0;
        }
        res = res > positive ? res : positive;
    }
    cout << res;
    return 0;
}

package main

import (
    "fmt"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var n int
    fmt.Scan(&n)
    positive,negative:=0,0
    max:=0
    var x int
    for n>0{
        fmt.Fscan(in,&x)
        if x>0{
            positive++
            if negative!=0{
                negative++
            }
        }else if x<0{
            tmp1,tmp2:=positive,negative
            if tmp2==0{
                positive=0
            }else{
                positive=tmp2+1
            }
            if tmp1==0{
                negative=1
            }else{
                negative=tmp1+1
            }
        }else{
            positive=0
            negative=0
        }
        if positive>max{
            max=positive
        }
        n--
    }
    fmt.Print(max)
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for(int i = 0; i < array.length; i++) {
                array[i] = in.nextInt();
            }
            System.out.println(getMaxMulLen(array));
        }
    }
    public static int getMaxMulLen(int[] array) {
        int n = array.length;
        // 状态: 以当前数字结尾的最长 (乘积为正/负) 的连续子数组

        int up = 0; // 统计正数最长子数组
        int down = 0; // 统计负数最长子数组
        int maxLen = 0;
        for(int i = 1; i <= n; i++) {
            int num = array[i - 1];
            if(num > 0) {
                // 更新正数最长子数组
                up += 1;
                // 更新负数最长子数组: 在 down[i - 1] 的基础上更新
                down = down == 0 ? 0 : down + 1;
            } else if(num < 0) {
                // 因为此处交叉更新, 所以需要先保留上一次的值
                int preD = down;
                // 更新负数最长子数组: up[i - 1] + 1
                down = up + 1;
                // 更新正数最长子数组: 在 down[i - 1] 的基础上更新
                up = preD == 0 ? 0 : preD + 1;
            } else {
                // 遇到 0 , 重新开始统计
                up = 0;
                down = 0;
            }
            // 更新正数最大长度
            maxLen = Math.max(maxLen, up);
        }
        return maxLen;
    }
}

while ((n = +readline())) {
  lines = readline().split(" ");
  lines.forEach(function (ele, index) {
    lines[index] = +ele;
  });
  var x = 0,
    y = 0,
    max = 0,
    min = 0;
  var flag = true;
  for (let i = 0; i < n; i++) {
    if (lines[i] > 0) {
      x++;
      y++;
      max = x > max ? x : max;
    } else if (lines[i] < 0) {
      if (flag) {
          x = 0;
          y++;
          flag = false;
      } else {
        var temp = y;
        y = ++x;
        x = ++temp;
        max = x > max ? x : max;
      }
    } else if (lines[i] == 0) {
      x = 0;
      y = 0;
        flag = true;
    }
  }
  console.log(max);
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    
    if (n < 1 || n > 100000)
        return -1;
    
    vector<int> arr;
    int val;
    for (int i = 0; i < n; ++i)
    {
        cin >> val;
        arr.push_back(val);
    }
    
    if (n == 1)
    {
        cout << arr[0];
        return 0;
    }
    
    int positive = arr[0] >= 0 ? 1 : 0, negtive = arr[0] <= 0 ? 1 : 0;
    int res = 0;
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] > 0)
        {
            // 如果当前乘的是正数，且前一个乘积为正，那么当前乘积仍为正，乘积为正数的子数组长度+1
            //                     前一个乘积为0，从当前开始计数，那么乘积为正数的子数组长度=1
            positive = positive >= 1 ? ++positive : 1;
            // 如果当前乘的是正数，且前一个乘积为负，那么当前乘积仍为负，乘积为负数的子数组长度+1
            //                     前一个乘积为0，那么乘积为负数的子数组长度=0
            negtive = negtive >= 1 ? ++negtive : 0;
        }
        else if (arr[i] < 0)
        {
            int temp = positive;
            
            // 如果当前乘的是负数，且前一个乘积为负，那么当前乘积为正，乘积为正数的子数组长度=乘积为负的子数组长度+1
            //                     前一个乘积为0，那么乘积为正数的子数组长度=0
            positive = negtive >= 1 ? ++negtive : 0;
            
            // 如果当前乘的是负数，且前一个乘积为正，那么当前乘积为负，乘积为负数的子数组长度=乘积为正的子数组长度+1
            //                     前一个乘积为0，从当前开始计数，那么乘积为负数的子数组长度=1
            negtive = temp >= 1 ? ++temp : 1;
        }
        else        // arr[i] = 0
        {
            // 如果当前乘的是0，不论前一个乘积为多少，乘积为负数的子数组长度和乘积为正的子数组长度均清零
            positive = 0;
            negtive = 0;
        }
        res = max(res, positive);
    }
    
    cout << res;
    
    return 0;
}

n = int(input().strip())
lst = list(map(int, input().split(' ')))
count = 0
#计算负数个数
for i in lst:
    if i < 0:
        count += 1
#负数为偶数个，那最大子集为本身
if count%2 == 0:
    print(n)
else:
    #寻找最靠近头、尾的一个负数的位置
    for j in range(1, int(n/2 + 1)):
        if (lst[j-1]<0)&nbs***bsp;(lst[-j] < 0):
            print(n-j)
            break
    #本解法没有考虑出现0的情况，故未完全通过

#include<iostream>
using namespace std;

// dp_pos[i]=  a[i]>0                 ? dp_pos[i-1]+1
//           : a[i]<0 && dp_neg[i]!=0 ? dp_neg[i-1]+1
//           : 0
// dp_neg[i]=  a[i]>0 && dp_neg[i]!=0 ? dp_neg[i-1]+1
//           : a[i]<0                 ? dp_pos[i-1]+1
//           : 0
// dp_pos[-1]=0
// dp_neg[-1]=0

int main(){
    int n,a,res=0,dpp=0,dpn=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        if(a>0){
            dpp=dpp+1;
            dpn=dpn!=0?dpn+1:dpn;
        }else if(a<0){
            int dpp_new=dpn!=0?dpn+1:dpn;
            dpn=dpp+1;
            dpp=dpp_new;
        }else{ // a==0
            dpp=0;
            dpn=0;
        }
        res=max(res,dpp);
    }
    cout<<res<<endl;
}

import java.io.*;
import java.util.*;
/*
最长乘积为正数的子数组长度
arr[i] 当前第i个位置数分正负，与前面的结果相互影响，求出最大正数，需要分正负两种状态
转态转移：
      dp[i][0] 以i为结尾的负数最长长度 
      dp[i][1] 以i为结尾正数最长长度
if(arr[i]<0)
    dp[i][0] = dp[i-1][1]+1;  // - * + = -
    dp[i][1] = dp[i-1][0]+1;  // - * - = +
else if(arr[i]>0)
     dp[i][0] = dp[i-1][0]+1;  // -*+ = -
     dp[i][1] = dp[i-1][1]+1; // +*+ = +
else  // +*0=0
    dp[i][0] = 0; 
    dp[i][1] = 0;
边界：
程序会出错。没有考虑+-长度为0的情况。 即
当dp[i-1][0]等于0时且arr[i]>0时，dp[i][0]=0 而不是1
每次判断需要添加正负长度时否是0。
if(arr[i]<0)
    dp[i+1][0] = dp[i][1]==0?1:dp[i][1]+1;  
    dp[i + 1][1] = dp[i][0]==0?0:dp[i][0]+1;  
if(arr[i]>0) 
    dp[i+1][0] = dp[i][0]==0?0:dp[i][0]+1;
    dp[i + 1][1] = dp[i][1]==0?1:dp[i][1]+1;
if(arr[i]==0)
    dp[i+1][0] = 0;
    dp[i+1][1] = 0;
*/
public class Main {
    public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        int[][] dp = new int[n+1][2];
        int res=Integer.MIN_VALUE;
        for(int i=0;i<n;i++) {
            if(arr[i]<0){
                dp[i+1][0] = dp[i][1]==0?1:dp[i][1]+1;  
                dp[i + 1][1] = dp[i][0]==0?0:dp[i][0]+1;  
            }else if(arr[i]>0) {
                dp[i+1][0] = dp[i][0]==0?0:dp[i][0]+1;
                dp[i + 1][1] = dp[i][1]==0?1:dp[i][1]+1;
            } else {
                dp[i+1][0] = 0;
                dp[i+1][1] = 0;
            }
            res = (int)Math.max(res, dp[i+1][1]);
        }
        System.out.println(res);
    }
}

let n = ~~readline()
let arr = readline().split(' ').map(x => parseInt(x))

function main(arr, n) {
    if (n === 1) return arr[0] > 0 ? 1 : 0
    // dp[0][i]表示以第i个数字结尾，乘积为正的累计子数组长度，
    // dp[1][i]表示乘积为负的子数组长度
    const dp = new Array(2).fill(0).map(() => new Array(n + 1).fill(0))
    for (let i = 1; i <= n; i++) {
        let x = arr[i - 1]
        // 如果是正数，更新dp[0][i]的值
        if (x > 0) {
            dp[0][i] = dp[0][i - 1] + 1
            // 如果负数部分不为0，则乘以正数，可以使得负数部分长度+1
            if (dp[1][i - 1] === 0) {
                // 之前乘积为负的部分长度为0，乘以正数长度还是为0
                dp[1][i] = 0
            } else {
                dp[1][i] = dp[1][i - 1] + 1
            }
        } else if (x < 0) {
            // 当为负值时，更新dp[1][i]的值为正数的值+1
            dp[1][i] = dp[0][i - 1] + 1
            // 更新正数的值，为负数的值+1，如果负数子数组长度为0，则为0
            if (dp[1][i - 1] === 0) {
                dp[0][i] = 0
            } else {
                dp[0][i] = dp[1][i - 1] + 1
            }
        }
    }
    return Math.max(...dp[0])
}

console.log(main(arr, n))

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] nums = new int[n];
            for(int i=0;i<nums.length;i++) {
                nums[i] = in.nextInt();
            }
            
            int[] dp = new int[n+1];
            int zeroNum = 0;
            int fushu = 0;
            for(int i=1;i<=n;i++) {
//                 if(nums[i-1] == 0) {
//                     System.out.print("0");
//                     return;
//                 }
                
                if(nums[i-1] > 0) {
                    
                    if(dp[i-1] == 0) {
                        dp[i] = 1;
                    } else {
                        dp[i] = dp[i-1] + 1;
                    }
                } else {
                    if(nums[i-1] ==0) {
                        zeroNum = i;
                        fushu = 0;
                        dp[i] = 0;
                    } else {
                        fushu++;
                        if(fushu % 2 == 0) {
                            dp[i] = i - zeroNum;
                        } else {
                            dp[i] = 0;
                        }
                    }
                }
            }
            
            int max = Integer.MIN_VALUE;
            for(int temp : dp) {
                max = Math.max(temp,max);
            }
            System.out.println(max);
        }
    }
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> a;
    int b;
    for(int i=0;i<n;i++)
    {
        cin>>b;
        a.push_back(b);
    }
    int positive=(a[0]>0)? 1:0;
    int negative=(a[0]<0)? 1:0;
    int temp;
    int maxnum=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0)
        {
            positive=positive+1;
            negative=(negative>0)? negative+1:0;
        }
        else if(a[i]==0)
        {
            positive=0;
            negative=0;
        }
        else
        {
            temp=(negative>0)? negative+1:0;
            negative=positive+1;
            positive=temp;         
        }
        maxnum=max(maxnum,positive);
    }
    cout<<maxnum<<endl;
    return 0;
}

//dp8乘积为正数的最长连续子数组
//其中positive[i]指的是以第i个数结尾的乘积为正的最长子序列长度
//其中negative[i]指的是以第i个数结尾的乘积为负的最长子序列长度
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int temp;
		int ans=0;
		int *num=(int *)malloc(sizeof(int)*(n+1));
		int *positive=(int *)malloc(sizeof(int)*(n+1));
		int *negative=(int *)malloc(sizeof(int)*(n+1));
		for(int i=1;i<=n;i++)
			scanf("%d",&num[i]);
		if(num[1]>0){
			positive[1]=1;
			negative[1]=0;
			ans=1;
		}
		else if(num[1]<0){
			positive[1]=0;
			negative[1]=1;
		}
		else{
			positive[1]=0;
			negative[1]=0;
		}
		for(int i=2;i<=n;i++){
			if(num[i]>0){
				positive[i]=positive[i-1]+1;
				negative[i]=((negative[i-1]>0)?negative[i-1]+1:0);
			}
			else if(num[i]<0){
				negative[i]=positive[i-1]+1;
				positive[i]=((negative[i-1]>0)?negative[i-1]+1:0);
			}
			else{
				positive[i]=0;
				negative[i]=0;
			}
			ans=max(ans,positive[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}