P1172 最大序列和 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

折翼的小鸟先生

2024年9月6日 16:21

最大序列和题解：

P1172

回复 0 | 赞 0 | 浏览 922

看了下数据范围，需要在O(n)下解决，区间和一眼维护前缀和做差即可，现在要求最大序列和，对于每一位前缀和，维护一下本身与其右边所有数的最小值，该位的前缀和与该其左侧的最小值的差值就是以该位为终点的前缀和最大值，遍历一遍整个前缀和序列，找到全部范围的最大值就行。 #include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<stack> #include<algorithm> using namespa...

2024年8月19日 18:06

最大序列和题解：动态规划

P1172

回复 0 | 赞 0 | 浏览 353

#include<bits/stdc++.h> using namespace std; int main() { long long n,t,sum=0,max=0; while(cin >> n){ long long dp[1000005]; for(int i=0;i<n;i++){ ...

我与代码的故事

2024年5月17日 00:08

最大序列和(75%的巨坑！！！（贪心）)题解：

P1172

回复 1 | 赞 2 | 浏览 564

题目中序列的值应该也是用long long存（用int存只能过75%），题目只给了序列和的数据范围，太折磨人了，害我WA好几次 #include<bits/stdc++.h> using namespace std; typedef long long LL; int n; int main() { while(~scanf("%d", &n)) { LL sum = 0; LL ans = LLONG_MIN; for(int i = 0; i <...

2024年4月23日 16:30

最大序列和题解：

P1172

回复 0 | 赞 0 | 浏览 364

#include <iostream> using namespace std; void dpList() { // 更改为 void 类型，因为没有返回值 int n; while (cin >> n) { // 处理多组输入 long long list[1000000]; long long dp[1000000]; &n...

2024年3月27日 16:16

最大序列和题解：

P1172

回复 0 | 赞 0 | 浏览 508

#include<iostream> using namespace std; long long dp[1000000]; long long list[1000000]; int main(){ int n; while(cin>>n){ for(int i = 0; i<n; i++){ cin>>list[i]; } long long res = -99999999; dp[0] = list[0]; for(int i = 0; i<n; i++){ dp[i...

2024年3月22日 12:27

最大序列和题解：全改为long long

P1172

回复 0 | 赞 0 | 浏览 720

#include <stdio.h> #include <stdlib.h> long long n; long long a[100000]; long long dp[100000]={0}; long long max(long long a ,long long b){ if(a>=b)return a; else return b; } int main() { while(scanf("%lld",&n)!...

2024年3月21日 19:54

最大序列和题解：

P1172

回复 0 | 赞 0 | 浏览 569

#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ long long s[n]; for(int i=0;i<n;i++)cin>>s[i]; &nbs...

2024年2月16日 17:58

最大序列和题解：新手题解

P1172

回复 4 | 赞 0 | 浏览 688

编译器不支持万能头文件，看了其他题解，直接把变量n放到定义数组里面报错这里用动态定义 #include <iostream> #include <string.h> #include <math.h> #include<vector> #include<algorithm> //#include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n) ...

2024年3月18日 16:47

最大序列和题解：时间超限怎么办

P1172

回复 2 | 赞 0 | 浏览 456

#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ int a[n]; int sum[n]={0}; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } int max=-1e9; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ int ...

2024年3月18日 17:20

最大序列和题解：和教学视频一样为什么只有75%

P1172

回复 1 | 赞 0 | 浏览 511

#include<bits/stdc++.h> using namespace std; int a[1000010]; int dp[1000010]; int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++){ cin>>a[i]; } dp[0]=a[0]; int maxx=a[0]; for(int i=...

1
2

题目最大序列和

题解数量19

热门题解

1 1172 最大序列合清华/兰大2019年机试

2 最大序列和题解：普通做法 &注意long long AC100%

3 最大序列和(75%的巨坑！！！（贪心）)题解：

4 1172-动态规划

5 最大序列和题解：

6 最大序列和题解：

7 最大序列和题解：全改为long long

8 最大序列和题解：动态规划

9 DP空间优化O(1)（时间236ms，内存140kb)

10 最大序列和题解：