0
已解决
中级启示者
题目描述 Description
给出一个长度为n的整数序列，里面有若干个整数，范围在-8~8之间。现在试求出其中一个连续子序列，满足该连续子序列乘积最大。
输入描述 Input Description
第一行，一个正整数n
第二行，n个用空格隔开的正整数，每个正整数在-8到8之间
输出描述 Output Description
连续子序列的最大乘积
WA 20
#include<iostream>
using namespace std;
int n;
long long f[25],ans,a[25];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
f[i]=max(f[i-1]*a[i],a[i]);
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}
0
已采纳
资深光能
我原来写了O（n^3），今天看到wwd发了个帖子，顺势dp了一发~~~
随手hack一组数据：
first:
7
3 5 -2 -5 3 -3 -4正确答案因为所有数的乘积5400，而你的代码答案是30 (酷町侠放过我，只不过搞个破解复制的扩展实再是太容易了~~)
second:
7
1 -3 2 5 1 -9 0（我刚开始改你的代码 有个点没考虑 只拿了30 菜/qwq）
设f[i]为从1~i必含i的连续乘积的最小值
设g[i]为从1~i必含i的连续乘积的最大值
状态转移方程：
f[i] = min(a[i], min(g[i-1]*a[i], f[i-1]*a[i]));
g[i] = max(a[i], max(f[i-1]*a[i], g[i-1]*a[i]));相信很好理解吧
每次
ans = max(ans, max(f[i], g[i]));哇，AC辣，开心**你辣
求采纳
0
中级天翼
我wa56,呃
0
被禁言
中级光能
是不是要考虑连续子序列不从第一项开始的情况
暴露一下，我也才20
张皓轩在2021-08-18 15:32:27追加了内容
建议用双重循环来枚举
0
缔造者
az，不知道how towrite
0
资深天翼
ding
0
缔造者之神
不知道怎么做
DING
0
资深守护
我wa40
