当前位置： 面试刷题>> Kadane 算法(经典算法150题)
### 题目描述
Kadane 算法是一种用于解决“最大子数组和”问题的线性时间复杂度算法。给定一个整数数组 `nums`，找到一个具有最大和的连续子数组（子数组至少包含一个元素），返回其最大和。
例如：
- 输入: `nums = [-2,1,-3,4,-1,2,1,-5,4]`
- 输出: `6`
解释：连续子数组 `[4,-1,2,1]` 的和最大，为 `6`。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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 中实现该算法，并给出了具体的示例输入和输出。在面试中，能够清晰地解释算法思想并给出正确的代码实现是非常重要的。