当前位置: 面试刷题>> 最大字数组 (经典算法题500道)


题目描述补充

题目:最大子数组(Maximum Subarray)

给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组至少包含一个元素),返回其最大和。

示例 1:

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

示例 2:

输入: nums = [1]
输出: 1

示例 3:

输入: nums = [5,4,-1,7,8]
输出: 23

PHP 代码示例

function maxSubArray($nums) {
    $maxSum = $nums[0];
    $currentSum = $nums[0];
    $length = count($nums);
    for ($i = 1; $i < $length; $i++) {
        $currentSum = max($nums[$i], $currentSum + $nums[$i]);
        $maxSum = max($maxSum, $currentSum);
    }
    return $maxSum;
}

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

Python 代码示例

def maxSubArray(nums):
    max_sum = nums[0]
    current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

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

JavaScript 代码示例

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

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

码小课网站中有更多相关内容分享给大家学习,包括算法基础、数据结构、面试技巧等,助力大家提升编程能力,顺利通过面试。

推荐面试题