题目描述

blablabla

样例

blablabla

算法1

动态规划做法：定义positiveCnt为以第索引i开头积为正的区间数量，negtiveCnt同理。
状态转移方程：
如果第i-1个元素为正，那么 positiveCnt[i] = positiveCnt[i - 1] -1 ，(-1是减去索引对（i-1,i-1））,
如果第i-1个元素为负，那么 positiveCnt[i] = negtiveCnt[i - 1] - 1;

时间复杂度

O(n)

java 代码

import java.util.Scanner;
public class Main {
    // 定义positiveCnt为以第索引i开头积为正的区间数量，negtiveCnt同理。
    static long temp, positiveCnt, negtiveCnt, posRes, negRes, mul = 1;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] nums = new int[n];
        // 先遍历一遍数组，求出以第一个元素开头的索引对为正和负的数量。
        for (int i = 0; i < n; ++i) {
            if (input.nextInt() > 0) nums[i] = 1;
            else nums[i] = -1;
            mul *= nums[i];
            if (mul > 0) ++positiveCnt;
            else ++negtiveCnt;
        }
        posRes = positiveCnt;
        negRes = negtiveCnt;
        // 状态转移：如果第i-1个元素为正，那么 positiveCnt[i] = positiveCnt[i - 1] -1,
        // 如果第i-1个元素为负，那么 positiveCnt[i] = negtiveCnt[i - 1] - 1
        for (int i = 1; i < n; ++i) {
            if(nums[i - 1] > 0) {
                --positiveCnt;
            }else {
                temp = positiveCnt;
                positiveCnt = negtiveCnt - 1;
                negtiveCnt = temp;
            }
            posRes += positiveCnt;
            negRes += negtiveCnt;
        }
        System.out.println(negRes + " " + posRes);

    }
}