1050 循環數組最大子段和

原题链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1050

如果没有循环的条件,那么我们可以用常规的方法算出最大的字段和max1

然后加上循环这个条件,我们可以先求出整个数组的和,然后在求出数组最小子段和,然后然后相减得到max2,然后和ans=max(max1,max2);

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std; 
#define inf -100
#define inf1 100
const int maxn=100;
int a[maxn];
int main()
{
    int n;
    __int64 sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    __int64 flag=a[0];
    __int64 ma=inf;
    for(int i=1;i<n;i++)
    {
        if(flag<0)
        flag=a[i];
        else
        flag+=a[i];
        if(ma<flag)
        ma=flag;
    }
    __int64 mi=inf1;
    flag=a[0];
    for(int i=1;i<n;i++)
    {
        if(flag>0)
        flag=a[i];
        else
        flag+=a[i];
        if(flag<mi) 
        mi=flag;
    }
    __int64 max1=max(sum,sum-mi);
    __int64 ans=max(max1,ma);
    printf("%I64d\n",ans);
}

 

更多相关文章
一周排行
  • 4.Controller默认激活    Controller对象的激活最终是通过注册的ControllerFactory完成的,当我们没有显示调用ControllerBuilder的SetControllerFact ...
  • Xtrabackup是由percona开发的一个开源软件,它是innodb热备工具ibbackup(收费的商业软件)的一个开源替代品.Xtrabackup由个部分组成:xtrabackup和innobackupex,
  • 


    		    雜談(6)記第一次線上會議(MSP培訓會議)
    (好气愤,刚刚快写好的这篇博客,没保存电脑竟然死机了!) 刚刚参与了MSP培训会议. 会议
  • 


    		    Chrome Beta for Mac&Linux正式發布下載
    不用翻译了吧,偷下懒...下载地址大家都知道,google的东西google一下. Goo ...
  • 用了非常多的时间来解决jbpm3.2发送邮件的问题,现在记录下来,以备后患,也希望能幫助到大家,闲话不多说,开始吧. 本书的例子采用的是高杰的<深入浅出jbpm>,版本为jbpm3.2,我本人的开发工具是 ...
  • 比较简单的动态规划啦,以前学动规时讲过,还知道另外一种方法,如果是求最大的矩形的话就只能用另外一中了,代码长些. /* ID: modengd1 PROG: bigbrn LANG: C++ */ #include
  • 今天在安装MYSQL的时候,新建数据库用户. #groupadd mysql 结果提示:bash: groupadd: command not found 是我变量不对吗?系统怎么会找不到groupadd 这条命令呢
  • 初步swift語言學習筆記9(OC與Swift雜)
    笔者:fengsh998原文地址:http://blog.csdn.net/fengsh9
  • 本来想写一篇关于golang io的笔记,但是在学习io之前必须了解array, slice, string概念,因此将在下篇写golang io.   array: 数组的长度是该数组类型的一部分,例如var bu ...
  • 詳解SPI中的極性CPOL和相位CPHA
    SPI由于接口相对简单(只需要4根线),用途算是比较广泛,主要应用在 EEPROM,FLA ...