题解 | #乘积为正数的最长连续子数组#

/*本人动规初学者，勿喷
本题解题思路：动规个人理解为寻找最优子结构，即构建状态转移方程，记录重复计算值，减少非必要计算次数
    本题计算乘积为正数的子数组长度，设置两个数组，分别用于记录0-n中的最长的正负子数组长度，仅仅只判断符号
     当传入两个数组的输入数组值inits[i]时，判断其正负，正数则正数数组直接加一，负数视情况看是否要置零
     inits[i]为负时同理，设置一个值ans来存储最大值
     当inits[i]输入为0时，正负数组都要置零，因为java数组默认初始化为0，所以直接空过这一次循环
     0不是正整数
*/

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception{
        StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter printWrit = new PrintWriter(new OutputStreamWriter(System.out));

        streamTokenizer.nextToken();
        int length = (int) streamTokenizer.nval;

        int ans = 0;
        int[] ints = new int[length];
        for (int i = 0; i < length; i++) {
            streamTokenizer.nextToken();
            ints[i] = (int) streamTokenizer.nval;
        }

        int[] dp1 = new int[length];//乘积为正的子序列长度
        int[] dp2 = new int[length];//乘积为负的子序列长度

        if (ints[0] >0){
            dp1[0] = 1;
        } else if (ints[0] < 0){
            dp2[0] = 1;
        }

        for (int i = 1; i < length; i++) {
            if (ints[i] >0){//判断序列
                dp1[i] = dp1[i-1] + 1; //当inits值为正时，乘积为正的子序列长度直接加一
                dp2[i] = dp2[i-1] >0 ? dp2[i-1] + 1 : 0; //当inits中值为正时，判定前一个数是否为负，否则归零重新判定
            }else if (ints[i] < 0){
                dp1[i] = dp2[i-1] >0 ? dp2[i-1] +1 : 0 ; //当inits为负时，正数序列判断负数的序列，如果之前的序列为负，则为正，反之重新计算
                dp2[i] = dp1[i-1] + 1; //判断值为负时，负数序列取决于正数序列
            }
            ans = Math.max(dp1[i],ans);
        }

        printWrit.println(ans);
        printWrit.flush();
    }
}