前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【HDU 1003】 Max Sum

【HDU 1003】 Max Sum

作者头像
饶文津
发布2020-06-02 14:38:11
3880
发布2020-06-02 14:38:11
举报
文章被收录于专栏:饶文津的专栏

题意

  需要在o(n)时间内,求最大连续的子序列的和,及其起点和终点。

分析

  一种方法是一边读,一边维护最小的前缀和 s[i] ,然后不断更新 ans = max(ans,s[j] - s[i]),以及起始位置。

  另一种方法是尺取(算是吧),l 和 r 代表起点和终点,一开始l=0,r=1,如果s[r]-s[l]>=0那就往右扫 r++,不断更新 ?ans = max(ans,s[r] - s[l]),以及起始位置,如果小于0了,那就舍弃前面这段了,也就是后面必然不用考虑它更划算,l=r,r++。还要注意全是负数的情况,那就只要输出最大的那个负数。

代码

维护min(s[i])

代码语言:javascript
复制
#include <cstdio>
#include <algorithm>

using namespace std;

int test,n;
int a,k,ans,s[100005],st,en;
int main()
{
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        s[0]=0;
        k=0;
        ans=-1001;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            s[i]=s[i-1]+a;
            if(s[i]-s[k]>ans){
                ans=s[i]-s[k];
                en=i;
                st=k+1;
            }
            if(s[i]<s[k]){
                k=i;
            }
        }
        if(t<test)printf("Case %d:\n%d %d %d\n\n",t,ans,st,en);
        else printf("Case %d:\n%d %d %d\n",t,ans,st,en);
    }
    return 0;
}

尺扫

代码语言:javascript
复制
#include <cstdio>
#include <algorithm>

using namespace std;

int test,n,a,ans,s[100005],st,en,maxa,maxp;
int main()
{
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        maxa=-1001;
        ans=0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            s[i]=s[i-1]+a;
            if(a>maxa)
            {
                maxa=a;
                maxp=i;
            }
        }
        if(maxa<0)
        {
            ans=maxa;
            st=en=maxp;
        }
        else
        {
            int l=0;
            int r=1;
            while(r <= n)
            {
                while(s[r] >= s[l] && r<n)
                {
                    r++;
                    if(s[r]-s[l]>ans)
                    {
                        ans=s[r]-s[l];
                        st=l+1;
                        en=r;
                    }
                }
                l=r;
                r++;
            }
        }
        if(t<test)printf("Case %d:\n%d %d %d\n\n",t,ans,st,en);
        else printf("Case %d:\n%d %d %d\n",t,ans,st,en);
    }
    return 0;
}
本文参与?腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-02-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客?前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体同步曝光计划? ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 分析
  • 代码
    • 维护min(s[i])
      • 尺扫
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
      http://www.vxiaotou.com