题目描述
最大子数组和问题:给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组至少包含一个元素),返回其最大和。
示例 1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
示例 2:
输入: nums = [1]
输出: 1
示例 3:
输入: nums = [0]
输出: 0
示例 4:
输入: nums = [-1]
输出: -1
提示:
1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5
解题思路
这个问题可以通过“Kadane's 算法”来解决,该算法的时间复杂度为 O(n),其中 n 是数组的长度。算法的基本思想是遍历数组,维护一个当前最大子数组和 currentMax
和一个全局最大子数组和 globalMax
。在遍历过程中,如果 currentMax
加上当前元素 nums[i]
的结果比 nums[i]
本身还小(即 currentMax + nums[i] < nums[i]
),则将 currentMax
更新为 nums[i]
,否则累加 nums[i]
到 currentMax
。同时,在每一步更新 currentMax
后,都要检查 currentMax
是否大于 globalMax
,并相应地更新 globalMax
。
示例代码
PHP
function maxSubArray($nums) {
$globalMax = $nums[0];
$currentMax = $nums[0];
for ($i = 1; $i < count($nums); $i++) {
$currentMax = max($nums[$i], $currentMax + $nums[$i]);
$globalMax = max($globalMax, $currentMax);
}
return $globalMax;
}
// 示例测试
$nums = [-2,1,-3,4,-1,2,1,-5,4];
echo maxSubArray($nums); // 输出 6
Python
def maxSubArray(nums):
globalMax = currentMax = nums[0]
for num in nums[1:]:
currentMax = max(num, currentMax + num)
globalMax = max(globalMax, currentMax)
return globalMax
# 示例测试
nums = [-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(nums)) # 输出 6
JavaScript
function maxSubArray(nums) {
let globalMax = nums[0];
let currentMax = nums[0];
for (let i = 1; i < nums.length; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
globalMax = Math.max(globalMax, currentMax);
}
return globalMax;
}
// 示例测试
const nums = [-2,1,-3,4,-1,2,1,-5,4];
console.log(maxSubArray(nums)); // 输出 6
以上代码示例分别用 PHP、Python 和 JavaScript 实现了求解最大子数组和的问题,符合题目要求,并且可以在码小课网站上作为教学示例发布。