2019牛客暑期多校训练营（第四场）C：sequence（思维+连续最大和）

【题解】

题意：给定两个长度为n的序列a,b，要求一段区间[l,r]的a的区间最小值与b的区间和乘积最大，输出这个乘积。

思路：首先，我们把区间长度为1的情况的答案跑一下，然后考虑区间大于1的情况。从使得乘积最大的a的区间最小值的正负来考虑：若此时最小值应为正值，那么显然我们需要尽可能大的>0的区间和，所以我们在跑区间和的时候如果sum<0，那么果断舍弃掉之前的区间和，更新sum和最小值min，因为负值显然会导致减少，我们要避免不必要的损失；若此时最小值应为负值，那么我们需要尽可能小的<0的区间和，所以我们要在sum>0的时候更新sum和min。在这两个过程中不断更新最大答案即可。

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e6+10;
ll ans,sum,mn;
ll a[maxn],b[maxn];
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    scanf("%lld",&b[1]);
    sum=b[1],mn=a[1];
    ans=b[1]*a[1];
    for(int i=2;i<=n;i++){ //最小值为正
        scanf("%lld",&b[i]);
        ans=max(ans,b[i]*a[i]); 
        if(sum<0)
            sum=b[i],mn=a[i];
        else{
            mn=min(mn,a[i]); //更新区间最小值
            sum+=b[i]; //更新区间和
            ans=max(ans,sum*mn);
        }
    }
    sum=b[1],mn=a[1];
    for(int i=2;i<=n;i++){ //最小值为负
        if(sum>0)
            sum=b[i],mn=a[i];
        else{
            mn=min(mn,a[i]);
            sum+=b[i];
            ans=max(ans,sum*mn);
        }
    }
    printf("%lld\n",ans);
    return 0;
}