首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

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就是最大的那个元素。 这样的话代码也是很简洁了:

01
您找到你想要的搜索结果了吗?
是的
没有找到
领券