🔗 LeetCode 53 - Maximum Subarray
📌 题目描述
给你一个整数数组 nums，请你找出一个具有最大和的 连续子数组，并返回其最大和。
🔍 示例
1
2
3
| 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
|
💡 解题思路：动态规划（Kadane’s Algorithm）
dp[i] 表示以 nums[i] 结尾的最大子数组和- 转移公式：
dp[i] = max(nums[i], dp[i-1] + nums[i])
- 可优化为 O(1) 空间，仅用两个变量
✅ JavaScript 实现
1
2
3
4
5
6
7
8
9
| var maxSubArray = function(nums) {
let maxSum = nums[0];
let currSum = nums[0];
for (let i = 1; i < nums.length; i++) {
currSum = Math.max(nums[i], currSum + nums[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
};
|
✅ Swift 实现
1
2
3
4
5
6
7
8
9
| func maxSubArray(_ nums: [Int]) -> Int {
var currSum = nums[0]
var maxSum = nums[0]
for i in 1..<nums.count {
currSum = max(nums[i], currSum + nums[i])
maxSum = max(maxSum, currSum)
}
return maxSum
}
|
🧠 思考拓展
- 如何返回最大子数组的下标范围？
- 如果数组是环形（头尾可以相连），如何求最大和？
- 分治法如何实现？（O(nlogn)）
