动态规划巧解最大子数组和(Python，Java，C++)

张开发
• 2026/4/19 7:35:03 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

动态规划巧解最大子数组和(Python，Java，C++)
题目LeetCode 53 最大子数组和给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组 [4,-1,2,1] 的和最大为 6Python解法动态规划from typing import List class Solution: def maxSubArray(self, nums: List[int])-int: currentSum nums[0] maxSum nums[0] for i in range(1, len(nums)): currentSum max(currentSum nums[i], nums[i]) maxSum max(maxSum, currentSum) return maxSum1.定义值cur nums[0] # 当前子数组的最大和max_sum nums[0] # 全局最大和2.循环核心# 核心要么重新开始要么接着前面累加cur max(nums[i], cur nums[i])# 更新全局最大值max_sum max(max_sum, cur)图形解释Java解法动态规划道理同Pythonclass Solution{ public int maxSubArray(int[] nums){ int currentSum nums[0]; int maxSum nums[0]; for(int i 1; i nums.length; i){ currentSum Math.max(currentSum nums[i], nums[i]); maxSum Math.max(maxSum, currentSum); } return maxSum; } }C解法动态规划class Solution { public: int maxSubArray(vectorint nums) { int cur nums[0]; int max_sum nums[0]; for(int i 1; i nums.size(); i){ cur max(cur nums[i], nums[i]); max_sum max(max_sum, cur); } return max_sum; } };

更多文章