vlambda博客
学习文章列表

题目

今天的题目是动态规划的。

题目一 leetcode53——最大子数组和

题目：>给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
子数组 是数组中的一个连续部分。 
示例 1： 
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]  
输出：6  
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 
示例 2： 
输入：nums = [1]  
输出：1  
示例 3： 
输入：nums = [5,4,-1,7,8]  
输出：23  
提示： 
1 <= nums.length <= 105  
-104 <= nums[i] <= 104  
题目跳转链接^[1] 

解题思路：

1. 方法一。动态规划。dp[i]表示以第i个元素结尾的最大连续子数组和（即必须包含第i个元素），dp[i]=max(dp[i-1]+nums[i], nums[i])，最后返回dp中最大的元素。

2. 方法二。分治法。没整明白，可以看官方的代码。

代码如下：

1# 参考网址：https://blog.csdn.net/qq_41286373/article/details/106411078
2class Solution:
3    def maxSubArray(self, nums: List[int]) -> int:
4        dp = [-float('inf') for _ in range(len(nums))]
5        for i in range(len(nums)):
6            dp[i] = max(dp[i-1]+nums[i], nums[i])
7        return max(dp)
8# 官方思路链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/