题目描述

Kadane 算法是一种用于解决“最大子数组和”问题的线性时间复杂度算法。给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。

例如：

• 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
• 输出: 6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

PHP 示例代码

function maxSubArray($nums) {
    $maxSoFar = $nums[0]; // 初始化最大和为数组的第一个元素
    $currentMax = $nums[0]; // 当前子数组的最大和

    for ($i = 1; $i < count($nums); $i++) {
        // 如果当前元素加上前一个子数组的和比当前元素大，则保留并继续累加
        // 否则，重新开始计算当前子数组的和
        $currentMax = max($nums[$i], $currentMax + $nums[$i]);
        // 更新全局最大和
        $maxSoFar = max($maxSoFar, $currentMax);
    }

    return $maxSoFar;
}

// 示例
$nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
echo maxSubArray($nums); // 输出 6

Python 示例代码

def maxSubArray(nums):
    max_so_far = nums[0]
    current_max = nums[0]

    for num in nums[1:]:
        current_max = max(num, current_max + num)
        max_so_far = max(max_so_far, current_max)

    return max_so_far

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出 6

JavaScript 示例代码

function maxSubArray(nums) {
    let maxSoFar = nums[0];
    let currentMax = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentMax = Math.max(nums[i], currentMax + nums[i]);
        maxSoFar = Math.max(maxSoFar, currentMax);
    }

    return maxSoFar;
}

// 示例
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // 输出 6

以上代码示例均实现了 Kadane 算法，用于解决最大子数组和问题。这些示例展示了如何在 PHP、Python 和 JavaScript 中实现该算法，并给出了具体的示例输入和输出。在面试中，能够清晰地解释算法思想并给出正确的代码实现是非常重要的。