ConanKIDの小窝

ConanKIDの小窝

最大子段积(笔记还是题解很纠结)

posted on 2020-05-08 20:05:37 | under 笔记还是题解呢 |

如果您想看懂这篇题解,那么先请$\color{green}{\operatorname{AC}}$ P1115 最大子段和 各位大佬肯定做过

现在的问题是,最大子段积。即给出一段序列,选出其中连续且非空的一段使得这段最大。

比如,输入P1115的样例,输出72

首先看到这道题,我想:跟最大子段和很像啊,先把最大子段和打出来再说吧。于是我就打了

#include<bits/stdc++.h>
using namespace std;
int maxn[200001];
int n,x;
int ans;
int main(){
    cin>>n;
    cin>>ans;
    maxn[1]=ans;
    for(int i=2;i<=n;i++){
        cin>>x;
        maxn[i]=max(maxn[i-1]+x,x);
        ans=max(ans,maxn[i]);
    }
    cout<<ans<<endl;
    return 0;
}

然后我想:不就是把和改成积了么,那我把状态转移方程里$+$改$\times$不就得了么。。。结果运行样例,输出3

肿麽回事?!

想了一下,发现:最大子段和的思想是,如果某一段和为负数,那么它一定对后面没有贡献了,因此可以直接“丢掉”,然后重打旗鼓另开张。但最大子段积不一样,如果某一段积为负数,那么它乘上一个负数之后,就变成了正数,对后面就有贡献了。因此,最大子段和的套路行不通。

进一步思考,又发现:如果负数乘负数可以“逆袭”超过原来结果,那么这两个负数的绝对值越大,乘出来的结果就越大。而负数的绝对值很大,就是这个数很小。

这里,思路已经呼之欲出了:记录当前最小值!

在原程序的基础上,增加一个$minn$数组,$minn_i$表示以第$i$个数结尾的字段中,积最小的一个。每次更新$maxn$数组时,状态转移方程里面取$\max$时,应该还要加上一个由$minn_{i-1}$而来的项,也就是minn[i-1]*x。同理,更新$minn$数组时,也应该有maxn[i-1]*x的项。

于是乎,问题迎刃而解。

#include<bits/stdc++.h>
using namespace std;
int n;
int maxn[100001];
int minn[100001];
int ans;
int x;
int main(){
    cin>>n;
    cin>>ans;
    maxn[1]=minn[1]=ans;
    for(int i=2;i<=n;i++){
        cin>>x;
        maxn[i]=max(max(maxn[i-1]*x,minn[i-1]*x),x);
        minn[i]=min(min(minn[i-1]*x,maxn[i-1]*x),x);
        ans=max(ans,maxn[i]);
    }
    cout<<ans<<endl;
    return 0;
}

因此,本人认为,打程序,不仅要会打,而且要完全理解算法的本质。就像此题,不知道最大子段和的思想,是做不出来的。