专栏首页chenjx85的技术专栏leetcode-53-Maximum Subarray(动态规划详解)

leetcode-53-Maximum Subarray(动态规划详解)

题目描述:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

要完成的函数:

int maxSubArray(vector<int>& nums) 

说明:

1、这是一道动态规划的题目。如果我们不使用动态规划,可能就要找出所有的子数组,然后一一判断,这是一件很恐怖的事情。

2、我们先说一下这道题要怎么做,最后再来总结动态规划的本质。

我们要选一个sum最大的子数组,我们碰到一个新的数字,比如处理完-2之后现在碰到1这个新的数字,我们有两种选择:

一是,把1加入到旧有的子数组中,“延续”下来,现在新的sum为-2+1=-1。

二是,废弃掉旧有的子数组,重新开始,以1为第一个元素,现在新的sum为1。

那很明显,我们处理完元素-2现在在处理元素1,我们更想要重新开始,无论之后还有什么元素,重新开始都比加入之前旧有子数组的结果要好。

这是一个局部最优解。

之后我们继续处理下一个元素-3,我们同样有两种选择:

一是,-3加入旧有子数组,现在新的sum为1-3=-2。

二是,重新开始,-3作为第一个元素,现在新的sum为-3。

很明显,我们更想要一的做法,“延续”旧有的子数组。

我们依然得到了当前状态的最优解……

后续照这种做法去做就好了。

代码如下:

    int maxSubArray(vector<int>& nums) 
    {
        int local=nums[0];//存储每一个阶段的最优解
        int global=nums[0];//存储整个过程能得到的最大sum
        for(int i=1;i<nums.size();i++)//从i=1开始
        {
            local=max(local+nums[i],nums[i]);//选择要“延续”还是“重新开始”
            global=max(global,local);
        }
        return global;
        
    }

上述代码实测13ms,beats 61.40% of cpp submissions。

对整个过程还不清晰的同学,不妨照着题目给的例子,自己写一遍程序运行结果,对整个过程会有更加清楚的认识。

3、动态规划的特性。

笔者也没有做过很多关于动态规划的题目,之前也只是接触过类似于viterbi这样的算法,这道题是第一次正儿八经的动态规划题。但我们仍可以管中窥豹,从中总结出动态规划的一些特性。

动态规划是单重循环,只需要从头到尾做一次遍历。

我们把一个过程分为多个阶段,比如题目给的例子,我们要处理的元素1是一个阶段,要处理的元素-3是一个阶段,要处理的元素4是一个阶段……

每个阶段可以由多个状态组成,比如我们要处理的元素1,第一个状态是加入到旧有的子数组,第二个状态是重新开始新的子数组。每个阶段都要选择一个新的状态,构成局部最优解。

我们从头到尾遍历了一遍,每一次都选择了每个阶段的局部最优解,最后我们得到的结果自然也是全局最优解。

关于时间复杂度和空间复杂度,动态规划远远优于“找到所有子数组,然后一一计算”的暴力解法。

假设我们有9个阶段,每个阶段2种状态。(题目给的例子)

使用动态规划算法,时间复杂度可以粗略认为是2+2+……+2+2=2*9=18;空间复杂度,每次只需要保存上一个阶段的局部最优解和当前全局最优解两个参数。

使用暴力解法,时间复杂度,必然要找出所有子数组,单个数字就有9种可能,2个数字的有8种可能,3个数字的有7种可能……已经远远超过动归的做法;空间复杂度方面也会超过动归的做法。

 动态规划真是个有趣的算法……

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-209-长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

    chenjx85
  • leetcode-73-矩阵置零

    给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

    chenjx85
  • leetcode-643-Maximum Average Subarray I

    chenjx85
  • leetcode-easy-array-删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    shengjk1
  • Leetcode 75 Sort Colors

    Given an array with n objects colored red, white or blue, sort them so that obj...

    triplebee
  • LeetCode1 两数之和

    itlemon
  • LeetCode之Jump Game II

    forrestlin
  • 删除排序数组中的重复数字Ⅱ

    一份执着✘
  • LeetCode 477 Total Hamming Distance

    The Hamming distance between two integers is the number of positions at which th...

    Yano_nankai
  • 【每日算法Day 90】5种方法:求解数组中出现次数超过一半的那个数

    这个方法最简单,用哈希表记录每个数字出现的次数,最后看哪个数字次数超过一半就行了。

    godweiyang

扫码关注云+社区

领取腾讯云代金券