做网站需要用什么语言开发,从零开始建设企业网站,广州机械加工,校园微信网站模板53. 最大子数组和 问题描述#xff1a;
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。
示例 1#xff1a; 输入#xff1a;nums [-… 53. 最大子数组和 问题描述
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。
示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。 提示
1 nums.length 10^5-10^4 nums[i] 10^4
问题分析
最近又遇到的老题目很简单大家都知道是dp但是如果真的是在面试环境上紧张了也许就漏了部分条件不能AC所以平时的基本功还是要打扎实的。具体思路 假设dp[i]表示以数组nums[i]结尾的最大子数组和那么dp[i]max{nums[i], dp[i−1]nums[i]}解释dp[i] 的值很显然有两种情况第1种情况为上一个状态dp[i−1] 加上当前值nums[i]第2种情况从当前值nums[i]重新起一个序列(重新开始)这两个种情况选择哪个呢咱们求的最值吗所以二者选取最大值。最后把整个dp遍历一般获取最大值即可。
Python3实现
# Time :2023/08/24
# Author :Liu
# 动态规划class Solution:def maxSubArray(self, nums):size len(nums)if size 0: return 0dp [0 for _ in range(size)]dp[0] nums[0]for i in range(1, size):dp[i] max(nums[i], dp[i-1] nums[i])return max(dp)举一反三
问题来了可能很多面试官不按照这个讨论出来牌如果把题目最后求解的要求改成子数组和的绝对值最大值那仔细想想也不难在维持一个和最小dp就可以了最后结合两个dp的结果返回。
Python3实现
# Time :2023/08/24
# Author :Liu
# 动态规划class Solution:def maxSubArray2(self, nums):size len(nums)if size 0: return 0dpmax [0 for _ in range(size)]dpmin [0 for _ in range(size)]dpmax[0] nums[0]dpmin[0] nums[0]for i in range(1, size):dpmax[i] max(nums[i], dpmax[i - 1] nums[i])dpmin[i] min(nums[i], dpmin[i - 1] nums[i])return max(abs(max(dpmax)), abs(min(dpmin)))if __name__ __main__:solu Solution()nums [-2, 1, -3, 4, -1, 2, 1, -5, 4, -10]print(solu.maxSubArray(nums)) # [-5, 4, -10] 11声明 总结学习有问题或不当之处可以批评指正哦谢谢。 题目链接https://leetcode.cn/problems/maximum-subarray/description/ 参考链接https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/
