P1172 最大序列和 - 题解

登录注册上岸

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

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

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

2024年2月16日 17:58

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

P1172

回复 4 | 赞 2 | 浏览 991

编译器不支持万能头文件，看了其他题解，直接把变量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 | 赞 1 | 浏览 868

#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 | 赞 1 | 浏览 905

#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=...

2024年3月13日 17:25

最大序列和题解：

P1172

回复 0 | 赞 3 | 浏览 1.2k

#include<stdio.h> int main() { long long a[1000000],dp[1000000];//dp[i]表示以a[i]结尾的最大序列和 long long max; long long n,i; while(~scanf("%lld",&n)) { ...

2024年3月12日 17:38

最大序列和题解：

P1172

回复 2 | 赞 0 | 浏览 943

这个代码为啥输出不正确啊，求大佬指点 #include<stdio.h> int main() { long long n,i; long long a[1000000]; while(scanf("%lld",&n)!=EOF) { long long sum=0; &nbs...

2024年1月21日 17:41

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

P1172

回复 0 | 赞 3 | 浏览 1.2k

#include <bits/stdc++.h> using namespace std; int main(){ int n; while(cin>>n){ long long sum = 0; long long res = INT_MIN; long long a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } for(auto i:a){ if(sum<0)sum=0; sum+=i; res = max(res,sum...

2023年8月5日 13:23

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

P1172

回复 0 | 赞 0 | 浏览 888

#include<cstdio> long a, dp, maxT;//64位机下long是8B，32位机是4B，注意细节 int main() { int n; while (scanf("%d", &n)!=EOF) { scanf("%ld", &a); maxT = dp = a;//初始化 for (int i = 1; i < n; i++) { scanf("%ld", &a); dp = (dp > 0)? (dp + a) : a; if (dp > maxT...

2023年4月13日 11:39

1172-动态规划

P1172

回复 0 | 赞 1 | 浏览 2.5k

这一题由于数据的原因一定要用longlong #include<iostream> #include<string> #include<vector> #include<algorithm> #include<string.h> #include <bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n){ long long a[n]; for(int i=0;i<...

2023年3月24日 21:20

最大连续子序列O(n)

P1172

回复 0 | 赞 0 | 浏览 2.2k

#include <iostream> using namespace std; int main() { int n; while(cin>>n){ long long *a=new long long[n]; for(int i=0;i<n;i++) cin>>a[i]; long long max=a[0],sum=0; for(int i=0;i<n;i++){ sum+=a[i]; if(sum<0) sum=0; if(sum>max)...

2022年7月19日 11:57

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

P1172

回复 0 | 赞 8 | 浏览 5.7k

这题归于动态规划，但是我之前怎么看都觉得是贪心今天想通了，可以从两种不同的角度来看：设dp[i]是以下标为i的元素为结尾的序列的最大合值 dp角度：遍历到第i个元素时，两种选择：要么选择第i个元素（dp[i-1]+list[i]），要么不选（之前的序列断开，重新开始计数）（list[i]），取最大值状态转移方程： dp[i]=max( dp[i-1]+list[i] , list[i] ); 最后再求出dp[n]中的最大值贪心角度：如果之前的序列合为负值，则说明对之后的序列合没有贡...

1
2
3

题目最大序列和

题解数量22

发布题解在线答疑

热门题解

1 最大序列和题解：dp思路

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

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

4 最大序列和题解：

5 最大序列和题解：

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

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

8 最大序列和题解：

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

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