`
SunnyYoona
  • 浏览: 361429 次
社区版块
存档分类
最新评论

[经典面试题][淘宝]求首尾相连数组的最大子数组和

 
阅读更多

题目

给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j],现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值(如果数组中的元素全部为负数,则最大和为0,即一个也没有选)。

输入:

输入包含多个测试用例,每个测试用例共有两行,第一行是一个整数n(1<=n<= 100000),表示数组的长度,第二行依次输入n个整数(整数绝对值不大于1000)。

输出:

对于每个测试用例,请输出子数组和的最大值。

样例输入:

6
1 -2 3 5 -1 2
5
6 -1 5 4 -7

样例输出:

10
14

思路一

[LeetCode]53.Maximum Subarray题目相类似,唯一区别是本题是首尾相连,首尾相连的数组难点是到达尾部后继续从头开始,比类似题目稍微复杂些。
这里采用拉长数组的方法避免了这些问题:将数组平铺为一个长度为2倍原先长度的的新数组,这样问题就变成了:求一个整型数组中长度不超过len(原数组长度)的子数组和的最大值,降低了难度。

代码

       /*---------------------------------------------
    *   日期:2015-02-20
    *   作者:SJF0115
    *   题目: 求首尾相连数组的最大子数组和
    *   来源:淘宝
    *   博客:
    -----------------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int MaxSubarray(int a[],int n){
            if(n <= 0){
                return 0;
            }//if
            int size = 2*n;
            // 构造2倍长度数组
            vector<int> num(a,a+n);
            for(int i = 0;i < n;++i){
                num.push_back(a[i]);
            }//for
            int max = 0;
            int sum = 0,start = 0,end = 0;
            for(int i = 0;i < size;++i){
                sum += num[i];
                if(sum < 0){
                    sum = 0;
                    start = i+1;
                }//if
                if(start >= n || (i - start + 1) > n){
                    break;
                }//if
                if(max < sum){
                    max = sum;
                    end = i;
                }//if
            }//for
            cout<<"最大数组["<<start%n<<","<<end<<"]"<<endl;
            return max;
        }
    };


    int main() {
        Solution solution;
        int num[] = {-1,-5,-4,-7};
        int result = solution.MaxSubarray(num,4);
        cout<<result<<endl;
    }

思路二

可以把问题的解分为两种情况:
(1)解没有跨过A[n-1]到A[0]
(2)解跨过A[n-1]到A[0]
对于这种情况,只要找到从A[0]开始和最大的一段(A[0]…..A[j])(0 <= j < n)
以及以A[n-1]结尾的和最大的一段(A[i]…..A[n-1])(0 <= i < n)
该种情况的最大值为A[i]+…..+A[n-1]+A[0]+….+A[j]
如果i <= j 则最大值为A[0]+…..+A[n-1]否则最大值为A[i]+…..+A[n-1]+A[0]+….+A[j]
最后,取两种情况的最大值就可以了。求解跨过A[n-1]到A[0]的情况只需要遍历数组一次,故总的时间复杂度为O(N)+O(N) = O(N)

代码

    /*---------------------------------------------
    *   日期:2015-02-20
    *   作者:SJF0115
    *   题目: 求首尾相连数组的最大子数组和
    *   来源:淘宝
    *   博客:
    -----------------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int MaxSubarray(int a[],int n){
            if(n <= 0){
                return 0;
            }//if
            int max = 0;
            int sum = 0,start = 0;
            // 第一种情况
            for(int i = 0;i < n;++i){
                sum += a[i];
                if(sum < 0){
                    sum = 0;
                    start = i+1;
                }//if
                if((i - start + 1) > n){
                    break;
                }//if
                if(max < sum){
                    max = sum;
                }//if
            }//for
            // 第二种情况
            int sumLeft = 0,sumRight = 0;
            int maxLeft = 0,maxRight = 0;
            int left = 0,right = n-1;
            // 以a[0]开头的最大连续和
            for(int i = 0;i < n;i++){
                sumLeft += a[i];
                if(sumLeft < 0){
                    break;
                }//if
                if(maxLeft < sumLeft){
                    maxLeft = sumLeft;
                    left = i;
                }//if
            }//for
            // 以a[n-1]结尾的最大连续和
            for(int j = n-1;j >= 0;--j){
                sumRight += a[j];
                if(sumRight < 0){
                    break;
                }//if
                if(maxRight < sumRight){
                    maxRight = sumRight;
                    right = j;
                }//if
            }//for
            if(left >= right){
                return max;
            }//if
            return max > (maxLeft + maxRight)?max:(maxLeft+maxRight);
        }
    };


    int main() {
        Solution solution;
        //int num[] = {1,-2,3,5,-1,2};
        //int num[] = {6,-1,5,4,-7};
        int num[] = {-1,-3,-4};
        int result = solution.MaxSubarray(num,3);
        cout<<result<<endl;
    }
<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>
分享到:
评论

相关推荐

    游泳圈的最大子矩阵和

    二维数组首尾相连,上下也相连,像个游泳圈或轮胎,又如何求最大子矩阵和? 如游泳圈展开成3行3列的二维矩阵: -18 10 7 1 -20 2 1 38 -2 那么最大的子矩阵和为:10+7+38-2=53 2 10 7 1 -20 2 1 38 -2 那么最大...

    西南交通大学计算机程序设计基础-实验12-C++.docx

    1、求sum=,其中x和n均为整数,由键盘输入。编程输出公式中的每一项的值、以及sum的值。要求:x, n, sum均用指针。 2.统计一维整型数组中能被3整除的元素个数,并输出。要求:数组元素随机产生(10~100),用指针...

    java 首尾相连的代码

    java 首尾相连 java 首尾相连 java 首尾相连

    javascript首尾相连滚动

    javascript实现的略缩图首尾相连滚动效果

    MangoDowner#clear-leetcode#面试题02.07.链表相交1

    面试题 02.07. 链表相交原题链接:面试题 02.07. 链表相交解法一:首尾相接法解题思路将这两个链表首尾相连,然后检测这个链表是否存在环,如果存在,则两

    11080游泳圈的最大子矩阵和

    二维数组首尾相连,上下也相连,像个游泳圈或轮胎,又如何求最大子矩阵和? 如游泳圈展开成3行3列的二维矩阵: -18 10 7 1 -20 2 1 38 -2 那么最大的子矩阵和为:10+7+38-2=53 2 10 7 1 -20 2 1 38 -2 那么最大的...

    浙江大学ACM题型分类

    1003 Numerical Summation of a Series 求最大公因子 math 1004 Anagrams by Stack 给出输入序列和若干输出序列,求栈的处理过程 stack 1005 JUGS 给两杯子,倒出n升水的最少步骤 搜索 1006 Do the Untwist  字符...

    数据结构期末复习习题.pptx

    顺序队列在实现的时候,通常将数组看成是一个首尾相连的环,这样做的目的是为了避免产生______现象 假溢出 数据结构期末复习习题全文共60页,当前为第5页。 5. 设有两个串p和q,其中q是p的子串,求q在p中首次出现的...

    分别用marquee和div+js实现首尾相连循环滚动效果,仅3行代码

    是本人2007年进行的一项研究,当时网络上没有什么既精简又实用的循环滚动代码,所以就自己琢磨了段时间,最终找到这个办法

    数据结构复习题1

    6.表达式a*(b+c)-d的后缀表达式是 2.求一个双链表长度的算法的时间复杂度为 3.在实现顺序队的时候,通常将数组看成是一个首尾相连的环,这样做的目的是为

    基于STM32的内部ADC对音频信号进行采样

    采用一根信号线控制首尾相连的8×10的WS2812 RGB LED阵列,每颗LED有24bit颜色深度,为了方便程序编写,这里只编写了全灭在内的25种不同亮度的不同颜色。 将二维数组显示在8×10的WS2812 RGB LED阵列上,电压越高颜色...

    Java范例开发大全 (源程序)

     实例66 求最大值、最小值和平均值 91  5.2 二维数组 92  实例67 二维数组的创建与使用 92  实例68 矩阵转置 93  实例69 奇数阶幻方 94  实例70 求方阵对角线之和 96  实例71 矩阵的加法 97  实例72 ...

    循环查找4个数之和最大值

    有一组数,其排列形式如下:11,19,9,12,5,20,1,18,4,16,6,10,15,2,17,3,14,7,13,8,且尾部8和头部11首尾相连,构成环形的一组数,编程找出相邻的4个数,其相加之和最大,并给出它们的起始位置。

    java范例开发大全(pdf&源码)

    实例66 求最大值、最小值和平均值 91 5.2 二维数组 92 实例67 二维数组的创建与使用 92 实例68 矩阵转置 93 实例69 奇数阶幻方 94 实例70 求方阵对角线之和 96 实例71 矩阵的加法 97 实例72 矩阵的减法 98 实例73 ...

    java范例开发大全源代码

     实例66 求最大值、最小值和平均值 91  5.2 二维数组 92  实例67 二维数组的创建与使用 92  实例68 矩阵转置 93  实例69 奇数阶幻方 94  实例70 求方阵对角线之和 96  实例71 矩阵的加法 97  ...

    java范例开发大全

    实例66 求最大值、最小值和平均值 91 5.2 二维数组 92 实例67 二维数组的创建与使用 92 实例68 矩阵转置 93 实例69 奇数阶幻方 94 实例70 求方阵对角线之和 96 实例71 矩阵的加法 97 实例72 矩阵的减法 98 实例73 ...

    非常好用的图片轮播插件(首尾相连)

    该插件支持垂直于水平方向的滚动,鼠标放上去会自动停住,鼠标移开自动移动,默认状态也会自己滑动。

    Java范例开发大全(全书源程序)

    实例66 求最大值、最小值和平均值 91 5.2 二维数组 92 实例67 二维数组的创建与使用 92 实例68 矩阵转置 93 实例69 奇数阶幻方 94 实例70 求方阵对角线之和 96 实例71 矩阵的加法 97 实例72 矩阵的减法 98 ...

    必看深度探索区块链

    必看深度探索区块链书籍,hyperledger技术与应用。

    JAVA实现约瑟夫出圈问题的解决

    约瑟夫出圈问题:(用数组实现) 由m个人围成首尾相连的圈报数,从第1个人开始报,报到n的人出圈,剩下的人继续从1开始报数,直到所有的人出圈为止。对于给定的m和n(从键盘上输入),求出所有人的出圈顺序。

Global site tag (gtag.js) - Google Analytics