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);
}

 

更多相关文章
一周排行
  • 本篇介绍OOP的第二个对象factory.在以往项目中其实真正使用klass的地方相当少,而factory则是十分常见的. 在smartjs中的factory并不是指的是工厂模式.在factory要求定义一个基础对象
  • 目前项目组在开发一个项目,由多个子模块构成,构建工具是maven,版本控制工具是svn.本文想对如何结合使用maven和svn提出一点初步的想法  一.只有svn的情况        首先考虑没有maven的情况.这
  • HDUOJSafecracker(1015)
    Safecracker Time Limit: 2/1 MS (Java/Others) 
  • Microsoft Office 家庭与学生版 2007 零售价:¥199(促销期间) 简体中文版 包含: Excel 2007 OneNote 2007 PowerPoint 2007 Word 2007 60天试 ...
  • 在我之前的博客20个最好的在线IDE中列举过很多在线IDE,可以很方便的在云端执行代码,这样在你手头没有编译器时想试个小程序会非常有用. 今天介绍的这个网站runnable把在线IDE和代码片段结合了起来,你可以在上
  • JAX-RS 2.0 REST客户端编程实例 2014/01/28 分类: 基础技术, 教程  0 条评论  标签: JAX-RS, RESTFUL 分享到:3 本文由 ImportNew - 靳禹 翻译自 hasc
  • 为某表做剔除整合处理,各行相关.起初使用 ICursor pCursor = pTable.Search(null,false); 语句查询,ICursor的第一行并没有指向表的第一行,虽然不是第一行, 只要顺序一致
  • iMac一體機安裝蘋果和Win7雙系統
    前几天,有个客户说有一苹果的一体机,想装苹果和Win7双系统.约好了时间,带上工具就过去了 ...
  • 1.文本框焦点问题 onBlur:当失去输入焦点后产生该事件 onFocus:当输入获得焦点后,产生该文件 Onchange:当文字值改变时,产生该事件 Onselect:当文字加亮后,产生该文件 <input ...
  • from:http://space.itpub.net/?uid-25744374-action-viewspace-itemid-732091 通过使用block change tracking功能,可以提高Ora ...