算法1

DP

设a为当前元素以正数结尾的,b为以负数结尾的. 具体看代码

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n ; cin>>n;int a=0,b=0;
    int lt = 0;
    long long int sa = 0 , sb = 0;
    for(int i = 0 ; i < n ;++i)
    {
        int x; cin>>x;
        if(x>0)
        {
            a+=1;
        }
        else
        {
            long long int t =a;
            a=b;
            b=1+t;
        }
        lt = x;
        sa+=a;sb+=b;
    }
    cout<<sb<<" "<<sa<<endl;
}