如何找到数组中最大子数组和，实现长尾词效果？

本文共计634个文字，预计阅读时间需要3分钟。

pythonclass Solution: def maxSubsequence(self, nums: List[int]) -> List[int]: # 创建一个dp数组，用来存储以每个元素结尾的最大子序列和 dp=[0] * len(nums) # 创建一个数组记录每个元素对应的最大子序列和 max_dp=[0] * len(nums)

# 初始化dp数组的第一个元素 dp[0]=nums[0] max_dp[0]=nums[0]

# 遍历数组，计算dp数组和max_dp数组 for i in range(1, len(nums)): # 如果当前元素大于前一个元素，则可以扩展前一个子序列 if nums[i] > nums[i - 1]: dp[i]=dp[i - 1] + nums[i] else: dp[i]=nums[i]

# 更新以当前元素结尾的最大子序列和 max_dp[i]=max(max_dp[i - 1], dp[i])

# 找到最大子序列和对应的索引 max_index=max_dp.index(max(max_dp))

# 返回以最大子序列和结尾的子序列 return nums[max_index:]

定义一个max保存遍历过程中出现的最大子数组和，也是返回结果，定义一个dp[i]，用来表示以第i个元素为结尾的数组的最大数组和。 一、题目大意

标签: 动态规划

leetcode.cn/problems/maximum-subarray

给你一个整数数组 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

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

二、解题思路

定义一个max保存遍历过程中出现的最大子数组和，也是返回结果，定义一个dp[i]，用来表示以第i个元素为结尾的数组的最大数组和。状态转移方程为：dp[i] = max(dp[i-1]+nums[i], nums[i])

三、解题方法 3.1 Java实现

public class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; int max = dp[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); max = Math.max(dp[i], max); } return max; } } 四、总结小记

• 2022/7/6 程序员是不是也有“文人相轻”的毛病