41. 最大子数组

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。 样例: 给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6 要求时间复杂度为O(n) 想了一会并没有特别好的方法,想了一个用双指针的方法,通过了大部分的数据测试,但是还是有不通过的,我也不知道错在哪里,待会贴在下面,先说正确的方法。 思路 先分析下这个问题啊,主要有三种情况: *1. 全部是负数,这就简单了,找到最大的负数就可以了。 *2. 全部是正数,也很简单,应该是把所有的数加起来就可以了。 *3. 有正也有负,最大子数组肯定是正的。 基于这三种情况分析,我们可以采用这样的思路,先设置一个max,把这个数设置为INT_MIN,设置sum作为变量来记录当前得到的字数组的和,一旦sum>max,就可以更新max,这样就能保证max是最大字数组的和,那么字数组如何更新呢,前面说了,如果有正数的话,最后的结果肯定是正的,那么我们遍历数组,把sum先初始化为第一个数,然后,从第二个数开始,如果发现前面的sum是负的,那么就可以把前面的字数组抛弃掉了,以当前的这个数作为新的字数组的起点,如果发现是正的,当前的这个数加入子数组,以此类推,这样就能找到最大字数组了。(每一次遍历的最后更新max)。 这样说来不是很直观,我们可以注意这样一个事实:我们要找的子数组的前面的几个数(不管是几个),和肯定不能是负的,如果是负的,那么去掉岂不是得到的和更大,这样就能理解为什么一旦发现前面的字数组为负的话,就丢掉,如果全负的话这种方式也是适合的,因为每次都会舍弃,sum的值就是当前元素,每次更新max,这样得到的max就是最大的那个元素。 这样的话代码也是很简洁了:

  int maxSubArray(vector<int> nums) {  
        if(nums.size()<=0){  
            return 0;  
        }   
        int max=INT_MIN,cur=0;     //c++最小值  
        for(int i=0; i<nums.size(); i++)    
        {    
            if(cur < 0)  
                cur = nums[i];  //如果前面加起来的和小于0,抛弃前面的  
            else  
                cur+=nums[i];  
  
            if(cur > max)  
                max = cur;  
        }    
        return max;    
          
    }  

我一开始想的另一种思路是:我把所有的数都先加起来,得到sum,然后用两个指针分别指向首尾,比较首尾元素的大小,总是把小的剔除掉(这样得到子数组和更大一些),字数组的和用sum减去剔除掉的数就可以了,如果两个数一样大,剔除掉任意一个就可以了(不能同时剔除两个‘比如[-1,-3,-1]',如果同时剔除两个1,得到的最大值可能是-3,实际上是-1,但是同时被剔除掉了),我是用这个方法试了一些数据,感觉还挺靠谱,于是写了一下,中间用迭代器的程序还不对,最后该用下标才对,也没有找到错误在哪里,这个程序还通过了70%的测试数据,最后还是没有对,目前还没有找到问题在哪,代码就贴在下面了,如果有人看到(应该没有),发现问题在哪,还望告知!

int maxSubArray(vector<int> &nums) {
        auto beg=nums.begin();
        auto end=nums.end()-1;
        int res_max=accumulate(nums.begin(),nums.end(),0);   //先把所有数求和
        int sum_num=res_max;
        while(beg!=end)
        {
            if(*beg<*end)
            {
              sum_num-=(*beg);
              beg++;
              if(sum_num>res_max)
              res_max=sum_num;
            }
            if(*beg>*end)
            {
                sum_num-=(*end);
                end--;
                if(sum_num>res_max)
                res_max=sum_num;
            }
            if(*beg==*end)
            {
                sum_num-=(*beg);
                beg++;
                sum_num-=(*end);
                end--;
                if(sum_num>res_max)
                res_max=sum_num;
            }
        }
        return res_max;
        // write your code here
    } 
    */
    
    
    int maxSubArray(vector<int> &nums) {
    int beg = 0;
    int end = nums.size() - 1;
    int res_max = accumulate(nums.begin(), nums.end(), 0);   //先把所有树求和
    int sum_num = res_max;
    while (beg<end)
    {
        cout << beg << "  " << end << endl;
        if (nums[beg]<nums[end])
        {
            sum_num -= (nums[beg]);
            beg++;
            if (sum_num>res_max)
                res_max = sum_num;
        }
        if (nums[beg]>nums[end])
        {
            sum_num -= (nums[end]);
            end--;
            if (sum_num>res_max)
                res_max = sum_num;
        }
        if (nums[beg] == nums[end])
        {
            sum_num -= (nums[beg]);
            beg++;
            sum_num -= (nums[end]);
            end--;
        }
    }
    return res_max;
    // write your code here
    }

振哥指导了一个思路说是当两端相同的话,任意去掉一个是不明智的,后来我想了一下确实是这样的,因为如果恰好有一个就是最大子数组之列又恰好被去掉呢,比如现在得到一个[2,-1,5,-3,2],最大字数组应该是[2,-1,5],但是我们这时候恰好把前面的2给去掉呢,这样得到的最大子数组只能是[5]了,这样显然是有问题的,嗯就是这样的。振哥英明。 one more question 我发现有个问题是一直被我忽略的,有时候在循环里写三个互斥的条件时,我很喜欢用三个if,就像这样:

while(--)
{
  if(--)  ---;
  if(--)  ---;
  if(--)  ---;
}

这样的写法有时候是很危险的,比如第一个if改变了第二个if里需要判断的某个值的话,这样就极有可能出错。而我们希望每次循环都只进入一个if,这里的三个if是分支结构,这个时候最好加上if,让逻辑更清晰一些:

while(--)
{
  if(--)  ---;
 else  if(--)  ---;
 else  if(--)  ---;
}

一般这种双指针的题,倒是可以用三个if,可能还效率高一些,因为即使第一个if里面出现了移动指针的情况,如果满足第二个if的话还是可以去移动指针的,因为即使这里用的是分支结构,通过while之后还是会进入倒第二个if里,但是为了保证逻辑上的正确,在判断的时候一定要记得着啦ing中结构的区别。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Coco的专栏

【优雅代码】深入浅出 妙用Javascript中apply、call、bind

9420
来自专栏个人随笔

深入理解Java异常处理机制 (笼统篇)

8710
来自专栏菩提树下的杨过

javascript中function调用时的参数检测常用办法

1.方法重载 js中并不直接支持类似c#的方法重载,所以只能变相的来解决,示意代码:(利用了内置属性arguments) var f1 = function(p...

22780
来自专栏racaljk

关于C++函数返回局部对象的详细分析

以前一直挺好奇的,C++是怎么在函数内返回一个局部对象的。因为按照我之前的想法,函数返回一个基本类型的值是通过存放到ecx实现的(关于浮点不了解),但是局部对象...

49810
来自专栏nummy

python operator模块学习

operator模块是python中内置的操作符函数接口,它定义了一些算术和比较内置操作的函数。operator模块是用c实现的,所以执行速度比python代码...

9120
来自专栏闪电gogogo的专栏

Python——正则表达式

此篇文章结合小甲鱼的笔记和视频整理。 1 编译 Python 通过 re 模块为正则表达式引擎提供一个接口,同时允许你将正则表达式编译成模式对象,并用它们来进行...

295100
来自专栏闪电gogogo的专栏

Python入门学习(二)

1 字典 1.1 字典的创建和访问 字典不同于前述的序列类型,它是一种映射类型。它的引入是为了简化定义索引值和元素值存在特定关系的定义和访问问题。 字典的定义形...

32780
来自专栏Python数据科学

Python爬虫之快速入门正则表达式

当完成了网页html的download之后,下一步当然是从网页中解析我们想要的数据了。那如何解析这些网页呢?Python中有许多种操作简单且高效的工具可以协助我...

13130
来自专栏Vamei实验室

Python基础05 缩进和选择

缩进 Python最具特色的是用缩进来标明成块的代码。我下面以if选择结构来举例。if后面跟随条件,如果条件成立,则执行归属于if的一个代码块。 先看C语言的表...

22690
来自专栏C/C++基础

C/C++数组与指针详解

数组大小(元素个数)一般在编译时决定,也有少部分编译器可以运行时动态决定数组大小,比如icpc(Intel C++编译器)。

15620

扫码关注云+社区

领取腾讯云代金券