51Nod1050 循环数组最大子段和

2020-12-13 20:19

阅读：543

标签：with min fine code 最大 iostream std 负数中间

Problem

N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。
例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

Solution

最大字段和最大，或者去掉中间某个最小字段和剩下的最大。

Code

#include
#include
#include
#include
typedef long long ll;
typedef long double ld;
typedef double db;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int n;
ll a[50020];
ll fmn[50020],fmx[50020],mn=0,mx=0,sum;
int main() {
    io_opt;
    cin>>n;
    for(int i=1;i>a[i];
        sum+=a[i];
        fmx[i]=max(a[i],fmx[i-1]+a[i]);
        mx=max(mx,fmx[i]);
        fmn[i]=min(a[i],fmn[i-1]+a[i]);
        mn=min(mn,fmn[i]);
    }
    cout

51Nod1050 循环数组最大子段和

标签：with min fine code 最大 iostream std 负数中间

原文地址：https://www.cnblogs.com/sz-wcc/p/11727716.html

上一篇：Servlet.service() for servlet [dispatcherServlet] in context with path [] threw exception [Request p

下一篇：C#默认以管理员身份运行程序实现代码

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：51Nod1050 循环数组最大子段和
文章链接：http://soscw.com/index.php/essay/36698.html

亲，登录后才可以留言！

51Nod1050 循环数组最大子段和

Problem

Solution

Code

评论

热门文章

推荐文章

最新文章

置顶文章