文档章节

HDOJ 1003:求一串数字中和最大的连续子串

北风其凉
 北风其凉
发布于 2014/08/09 13:01
字数 615
阅读 73
收藏 0

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1003

一、题目要求

给出几组整型数据,每组数据在最开始都会给出数据的数量,根据给出的数据,求这组数据中最大的连续子串的和是多少,并写出此时子串的左、右边界(输出的左右边界从1起算)

二、程序代码

代码思路详见注释

#include<iostream>

using namespace std;

int main()
{
    int counter;     //计数器
    int countera;    //计数器a,用于统计一共有多少组数据
    int counterb;    //计数器b,用于统计每组数据中的数据数
    int i, j;        //for语句遍历用变量
    int sum;         //临时计算的各数字和
    int maxsum;      //数字串中的最大子串和
    int left, right; //取最大子串和时的左边界和右边界

    cin >> countera;
    for(counter = 1; counter <= countera; counter++)
    {
        maxsum = -1001;

        //依次读入数据时,maxsum被设置为数组中的最大值
        cin >> counterb;
        int* array = new int[counterb];
        for(i = 0; i < counterb; i++)
        {
            cin >> array[i];
            if(array[i] > maxsum)
            {
                maxsum = array[i];
                left = i;
                right = i;
            }
        }

        for(i = 0; i < counterb; i++)
        {
            //除了自己单独成串的情况(前面已经考虑过)
            //负数不能作为max子串的第0项
            if(array[i] < 0)
            {
                continue;
            }

            //考察从数组array第i项开始的各子串
            sum = 0;
            for(j = i; j < counterb; j++)
            {
                sum += array[j];
                //子串数字和大于maxsum的情况下
                //将maxsum与左右边界设定为当前状态
                if(sum > maxsum)
                {
                    maxsum = sum;
                    left = i;
                    right = j;
                }
                //如果sum小于0,则后面的子串不必考察
                //因为后面的串再大,加上前面小于0的sum也是累赘
                //不可能再得出新的最大子串
                if(sum < 0)
                {
                    break;
                }
            }
        }

        //输出计算结果
        cout << "Case " << counter << ':' << endl;
        cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;
        if(counter != countera)
        {
            cout << endl;
        }
    }

    return 0;
}

三、之前写的超时代码(穷举法)

#include<iostream>

using namespace std;

int main()
{
    int counter, countera, counterb;
    int i, j, k, sum, maxsum, left, right;

    //读取数据组数
    cin >> countera;
    for(counter = 1; counter <= countera; counter++)
    {
        //依次读入各组数据
        cin >> counterb;
        int* array = new int[counterb];
        for(i = 0; i < counterb; i++)
        {
            cin >> array[i];
        }

        maxsum = array[0];
        //逐个子串比对
        for(i = 0; i < counterb; i++)
        {
            for(j = i; j < counterb; j++)
            {
                //计算子串数字和
                sum = 0;
                for(k = i; k <= j; k++)
                {
                    sum += array[k];
                }
                //数字和大于maxsum则更新maxsum
                if(sum > maxsum)
                {
                    left = i;
                    right = j;
                    maxsum = sum;
                }
            }
        }

        cout << "Case " << counter << ':' << endl;
        cout << maxsum << ' ' << left + 1 << ' ' << right + 1 << endl;
        if(counter != countera)
        {
            cout << endl;
        }
    }

    return 0;
}

END

© 著作权归作者所有

北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
Google 面试题 | 数组的度数

专栏 | 九章算法 网址 | http://www.jiuzhang.com 1.题目描述 给定元素全为非负整数的非空数组nums,数组的度等于出现最多的元素的次数。找到具有和nums相同度的连续子串的最小长度。 样 例 ...

2018/02/24
0
0
求3个元素把一串数字均分为4个子串,其和相等

题目: 给定一串数字 判断是否存在这三个元素,它们将数字串分为四个子串,其中每个子串的数字之和均相同(该3个元素不纳入计算) 要求时间复杂度和空间复杂度均不能超过O(n) 注意是利用左右两...

messud4312
2018/04/12
0
0
请教个连续子串的算法问题

给出一串不重复的整数数组,算出其中的连续子串堆,堆内部可以乱序。 比如有一串不重复整数:15,4,1,3,2,6,5,13,-7,-8,-6,10 则得到的结果是4,1,3,2,6,5和-7,-8,-6这两个子串 如果给出的数组...

RAY_STONE
2013/06/20
176
5

没有更多内容

加载失败,请刷新页面

加载更多

GMTC2019|闲鱼-基于Flutter的架构演进与创新

作者:闲鱼技术-宗心 2012年应届毕业加入阿里巴巴,主导了闲鱼基于Flutter的新混合架构,同时推进了Flutter在闲鱼各业务线的落地。未来将持续关注终端技术的演变及趋势 Flutter的优势与挑战 ...

阿里云云栖社区
27分钟前
2
0
迪蒙人工智能共享停车吸引国际关注

  近来,华为创始人任正非多次提及人工智能。即便在华为生死攸关的关键时刻,任正非依旧不忘强调教育的重要性,“如果不重视教育,实际上我们会重返贫穷的,因为这个社会,最终是要走向人工智能的...

琴殇的
28分钟前
0
0
iOS开发之EventKitUI框架的应用

iOS开发之EventKitUI框架的应用 前面博客,有介绍EventKit这个框架的使用,使用EventKit可以与系统的日历和提醒应用进行交互,读写用户的日程事件。EventKitUI,顾名思义,其实基于EventKit框...

珲少
36分钟前
0
0
从MySQL源码看其网络IO模型

从MySQL源码看其网络IO模型 前言 MySQL是当今最流行的开源数据库,阅读其源码是一件大有裨益的事情(虽然其代码感觉比较凌乱)。而笔者阅读一个Server源码的习惯就是先从其网络IO模型看起。于是...

无毁的湖光-Al
37分钟前
0
0
WebService学习笔记

什么是Web Services? Web Services 是应用程序组件 Web Services 使用开放协议进行通信 Web Services 是独立的(self-contained)并可自我描述 Web Services 可通过使用UDDI来发现 Web Serv...

榴莲黑芝麻糊
53分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部