最大子段和
2025-01-24 19:15:35
发布于：上海
4阅读
0回复
0点赞
前缀和 维护前缀最小
#include <bits/stdc++.h>
using namespace std;
long long n,ans=-0x3f3f3f3f;
long long a[100010],sum[100010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i] = sum[i-1] + a[i];
}
long long mn = 0;
for(int i=1;i<=n;i++){
ans = max(ans,sum[i] - mn);
mn = min(sum[i],mn);
}
cout<<ans;
}
动态规划 思路背包
#include <bits/stdc++.h>
using namespace std;
long long n,ans=-0x3f3f3f3f,a[100010];
long long dp[100010]; //到达当前i点的最大子段和
// dp[i] = dp[i-1] + a[i];
// dp[i] = a[i];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i] = -1e18;
}
dp[0] = 0;
long long ans = -1e18;
for(int i=1;i<=n;i++){
dp[i] = max(dp[i-1]+a[i],a[i]);
ans=max(ans,dp[i]);
}
cout<<ans;
}
这里空空如也
有帮助，赞一个