欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣剑指offer第42题.连续子数组的最大值题解

程序员文章站 2022-04-11 19:00:37
...

题目

力扣剑指offer第42题.连续子数组的最大值题解

思路

这道题用到了动态规划的思路,私认为动态规划从开销上是优胜于分治算法的。
我们可以从最暴力的双重for循环开始寻找思路。暴力算法无非就是固定一个下标值,找出这个下标到数组末尾的这么多个子数组中,值最大的一种情况。
但是我们在暴力的过程中是可以发现,有些情况是直接可以摒弃的。比如当前的下标所对应的值是负数时,会拖累到子数组后面的部分,就应该摒弃。
于是,改良后的动态规划算法也呼之欲出。
我们从头开始遍历,设置一个储存最终结果的数ans,以及储存临时子数组元素的和值的数tmp。
我们进行迭代时,首先判断当前的tmp值是否小于0,如果小于0,tmp=nums[i],即把前面的子数组“断开”,以当前i节点建立新的子数组,并赋值给tmp;否则,继续延长子数组,tmp+=nums[i]。
迭代的每一个回合,都更新一次ans的值。
这样子,我们经过O(n)的复杂度,就可以实现寻找连续子数组的最大值的目标。
其实这道题有个变种,就是把输出最大值,改成输出有最大值的子数组。不过换汤不换药,定义一个vector储存子数组即可解决。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums.size()==1)return nums[0];
        int len=nums.size();
        int ans=-1e9;
        int tmp=nums[0];
        ans=max(ans,tmp);
        for(int i=1;i<len;i++){
            tmp+=nums[i];
            
            if(tmp<nums[i]){
                tmp=nums[i];
            }
            ans=max(ans,tmp);
        }
        return ans;
    }
};