Loading...
墨滴

程序员小熊

2021/06/14  阅读:31  主题:全栈蓝

最大子序和

前言

大家好,我是来自华为程序员小熊。清明假期马上就要结束了,小熊给大家带来一道笔试和面试中与动态规划相关的常考的简单题,这道题被字节、微软、亚马逊和苹果等各大互联网大厂作为笔试题。

这道题就是 Leetcode 的第 53 题-最大子序和,了解动态规划的童鞋,在看到最大两个字的时候,很容易就会想到用动态规划去解答,因为涉及到最优解的问题,一般都可以通过动归去做。本题小熊提供动态规划的思路供大家参考,希望对大家有所帮助。

题目

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),

返回其最大和。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

提示:

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5

解题思路

本题是一道典型的动态规划的题,因此采用动态规划的策略去解答。

定义状态 dp[i]:以 nums[i]结尾(包含 nums[i])的连续子数组的最大和。

状态转移方程 dp[i] = max(dp[i - 1] + nums[i], nums[i]),其中 i >= 1,当 dp[i - 1] < 0 时,抛弃当前的和最大的连续子数组,从 nums[i] 开始,重新寻找和最大的连续子数组,否则,将 nums[i] 加入到当前的和最大的连续子数组。

边界条件 dp[0] = nums[0]。

举栗

以数组 nums[i] = [-2,1,-3,4,-1,2,1,-5,4] 为例子,如下图示。

示例
示例

从上图可以看出:dp[0] = nums[0] = -1 < 0,由于当前的连续子数组的最大和小于零,因此应该丢弃 num[0],从 nums[1] = 1 开始重新寻找和最大的连续子数组。

寻找和最大的连续子数组的完整动图如下所示:

完整动图
完整动图

由状态转移方程可知,dp[i] 只与 dp[i - 1] 和 nums[i] 相关,因此没必要再去定义 dp,直接复用 nums 即可。

Show me the Code

C++

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        nums[i] = max(nums[i - 1], 0) + nums[i];
        maxSum = max(maxSum, nums[i]);
    }

    return maxSum;
}

Java

int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    for (int i = 1; i < nums.length; ++i) {
        nums[i] = Math.max(nums[i - 1], 0) + nums[i];
        maxSum = Math.max(maxSum, nums[i]);
    }

    return maxSum;
}

Python3

def maxSubArray(self, nums: List[int]) -> int:
    for i in range(1, len(nums)):
        nums[i] = max(nums[i - 1], 0) + nums[i]
    
    return max(nums)

Golang

func maxSubArray(nums []int) int {
    maxSum := nums[0];
    for i := 1; i < len(nums); i++ {
        if nums[i - 1] > 0 {
            nums[i] += nums[i - 1]
        }

        if nums[i] > maxSum {
            maxSum = nums[i]
        }
    }

    return maxSum;
}

C

int maxSubArray(int* nums, int numsSize){
    int maxSum = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        nums[i] = fmax(nums[i - 1] + nums[i], nums[i]);
        maxSum = fmax(maxSum, nums[i]);
    }

    return maxSum;
}

复杂度分析

时间复杂度:O(n),其中 n 是数组的长度,遍历一遍数组。

空间复杂度:O(1),未开辟额外的存储空间。

往期动态规划相关精彩文章回顾

手撕腾讯面试题-乘积最大子数组

动态规划经典题之最长上升子序列最终版

动态规划经典题之最长上升子序列

到底是爬一阶还是爬两阶?

更多精彩

关注公众号程序员小熊 微信公众号

后台回复算法,即可获取高清无码的经典算法电子书~

后台回复C++,即可获取侯捷老师 C++ 经典视频教程~

后台回复python,即可获取高清无码的经典 python 电子书~

后台回复1024,即可获取三份来自 BAT 大佬的 Leetcode 刷题手册~

为了回馈读者,本公众号不定期会有送礼活动,敬请关注~

程序员小熊

2021/06/14  阅读:31  主题:全栈蓝

作者介绍

程序员小熊

公众号:程序员小熊,华为程序员