题目描述

最大子数组和问题：给定一个整数数组 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 实现了求解最大子数组和的问题，符合题目要求，并且可以在码小课网站上作为教学示例发布。