| 20702最大乘积 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
输入n个元素组成的序列s，你需要找出一个乘积最大的连续子序列，并输出这个序列的乘积，如果这个最大的乘积不是正数，应输出-1 (表示无解）。 |
|
输入
|
|
共两行，第一行包括一个正整数n，表示序列S的元素个数，第二行为序列S的n个元素，两两之间由一个空格分隔。
|
|
输出
|
|
题目要求的结果
|
|
输入示例
|
|
3
2 4 -3 |
|
输出示例
|
|
8
|
|
其他说明
|
|
数据范围：1≤n≤18,-10≤s≤10；。提示：结果的范围在long long范围内。
|
题解：窝萌把它当成O(N)来做有些价值：设mx[i],mi[i]表示以i为结尾的连续子序列的最大最小乘积。
窝萌的算法显然可以在线维护：读入一个数x，可以连击也可以从x开始，如果连击的话可以分正负两种情况转移（如果懒可以写到一块。。。）
WA了一发：窝萌认真地盯着这个式子，认真地盯着这个式子，认真地盯着这个式子：if(负数) then mx=max(x,mi*x);mi=min(x,mi*x);（已加滚动），发现是错误的，因为mx是会变的= =。算是提了个醒：如果想当然用了一个数组的滚动一定要关注哪些量被改变了= =。。。同时告诉窝萌，为啥不用两个数组的滚动？？！！做大死啊？？！！= =
哦对还有：write函数记得跟着改范围哦。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar(' ') 9 using namespace std; 10 const int maxn=20+5; 11 inline int read(){ 12 long long x=0,sig=1;char ch=getchar(); 13 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 14 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 15 return x*=sig; 16 } 17 inline void write(long long x){ 18 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 19 int len=0;long long buf[20];while(x)buf[len++]=x%10,x/=10; 20 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 21 } 22 int n;long long mi,mx; 23 void init(){ 24 n=read();long long x,ans,t; 25 x=read();mi=mx=ans=x; 26 for(int i=2;i<=n;i++){ 27 x=read(); 28 if(x>=0)mx=max(x,mx*x),mi=min(x,mi*x); 29 else t=mx,mx=max(x,mi*x),mi=min(x,t*x);//呵呵哦 30 ans=max(ans,mx); 31 } 32 if(ans<=0)write(-1);else write(ans); 33 return; 34 } 35 void work(){ 36 return; 37 } 38 void print(){ 39 return; 40 } 41 int main(){init();work();print();return 0;}