郑轻周赛（7）复盘，H题
前言：
这个题一开始感觉可以写出来的，样例也过了，但是超时了，比赛前刚学的前缀和，觉得这道题可以用前缀和来解决，但是还是逃不了二重循环遍历，可能刚学还是有点生疏。
题目：
问题 H: 大嘴猫吃金币
时间限制: 1 Sec 内存限制: 128 MB
题目描述
地面上有排成一条直线的n个金币，金币有不同的价值(甚至是负的)，大嘴猫想用它的大嘴来吃这些金币。但是大嘴猫只能张一次嘴，所以它只能吃连续一段的金币。你知道大嘴猫最多能吃多大价值的金币吗？
输入
第一行一个整数n，表示有n个金币 。1 <= n <= 1000000。输出
接下来n行每行一个整数x，表示金币的价值。x在int范围内。
一行一个整数，表示最多吃下金币的价值。
样例输入 Copy
4
1 2 -1 10
样例输出 Copy
12
分析：
答案分析：从前往后累加，同时维护最⼤值。因为要取sum最⼤的⼀段，所以当加上一个数sum⼩于0时，这一段就停止，让sum=0，跳过这个数从头开始计算下一段的sum。
比如：0 12 -13 14 0 不必考虑负数后面的和加起来为14，比这个负数 -13大，就去取sum为五个数之和，因为这不是最大的，直接跳过-13和前面一段的和为12，只取14，14就是最大的
我的题解：
#include<iostream>
using namespace std;
int n,m,a[1000010];
long long int sum;
int main()
{
long long int max=-1000000;
scanf("%d",&n);
a[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",m);
sum+=m;
a[i]=sum;//将前i项和储存在数组里，然后作差就可以得到一段距离的金币值
}
for(int i=n;i>=1;i--)//二重循环依次作差找最小值，这步就是超时的原因。。。复杂度是n的平方
{
for(int j=i-1;j>=0;j--)
{
if(a[i]-a[j]>max)
max=a[i]-a[j];
}
}
printf("%lld",max);
return 0;
}
答案题解：
#include<iostream>
using namespace std;
const int N = 1e6+5;
typedef long long ll;
int a[N];
ll max(ll a , ll b)
{
if(a > b)
return a;
return b;
}
int main()
{
int n;
scanf("%d",&n);
ll ans = 0 , sum = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(sum + a[i] >= 0)
sum += a[i];
else
sum = 0;
ans = max(ans,sum);
}
printf("%lld\n",ans);
return 0;
}
总结：
二重遍历循环时最笨也最耗时的，尽量不要用，比赛的时候多分析题意，将问题化简。
前缀和运用不熟练，要多加练习题目。
投递拼多多集团-PDD等公司10个岗位 >
点点互动一面8人在聊
