线性动态规划

#include<bits/stdc++.h>
using namespace std;
const int N=100050;
long long n,a[N],b[N],f[N],maxa=LONG_LONG_MIN,minb=LONG_LONG_MAX;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>f[i];
    a[1]=f[1],b[1]=f[1];
    for(int i=2;i<=n;i++)
    {
        a[i]=max(max(b[i-1]*f[i],a[i-1]*f[i]),f[i]);
        b[i]=min(min(b[i-1]*f[i],a[i-1]*f[i]),f[i]);
        maxa=max(maxa,a[i]),minb=min(minb,b[i]);
    }
    maxa=max(maxa,a[1]);
    minb=min(minb,b[1]);
    cout<<maxa<<endl<<minb;
    return 0;
}