最大子数组和

题目要求

给定一个整数数组 nums，任务是找到一个具有最大和的连续子数组（至少包含一个元素），并返回这个最大和。

解题思路

解决这个问题的一个经典方法是使用动态规划（DP）。以下是解题的步骤：

初始化状态：
- 创建一个名为 dp 的数组，用于存储到当前位置为止的最大子数组和。dp[i] 表示以 nums[i] 结尾的最大子数组和。
- 将 dp[0] 初始化为 nums[0]，因为第一个元素本身就是一个子数组。
- 创建一个变量 maxSum 来跟踪遍历过程中遇到的最大子数组和，并将其初始化为 dp[0]。
状态转移方程：
- 遍历数组 nums，从索引 1 到 n-1（n 是数组 nums 的长度）。
- 更新 dp[i] 为 max(nums[i], dp[i-1] + nums[i])。这表示对于每个元素 nums[i]，你可以选择只包含 nums[i] 自身，或者将 nums[i] 添加到以 nums[i-1] 结尾的最大子数组和中。
- 每次计算出新的 dp[i] 后，比较并更新 maxSum 为 max(maxSum, dp[i])。
优化存储空间：
- 注意到在状态转移方程中，dp[i] 只依赖于 dp[i-1]，因此不需要维护整个 dp 数组，只需使用一个变量 currentMax 来存储 dp[i-1] 的值即可。
- 更新 currentMax 为 max(nums[i], currentMax + nums[i])，然后更新 maxSum。
返回结果：
- 遍历完成后，maxSum 将包含最大子数组和，返回 maxSum 即可。

这个问题也被称为最大子序和问题，是一个经典的动态规划问题。Kadane 算法就是上述思路的实现，它的时间复杂度为 O(n)，空间复杂度为 O(1)，是解决这个问题的最有效方法。

Golang 版本

package main

import (
	"fmt"
)

func maxSubArray(nums []int) int {
	maxSum := nums[0]
	currentMax := nums[0]

	for i := 1; i < len(nums); i++ {
		currentMax = max(nums[i], currentMax+nums[i])
		maxSum = max(maxSum, currentMax)
	}

	return maxSum
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	fmt.Println("Maximum Subarray Sum:", maxSubArray(nums))
}

这段代码定义了一个 maxSubArray 函数，它接受一个整数数组 nums 并返回最大子数组的和。max 函数用于比较两个整数并返回较大的一个。在 main 函数中，我们定义了一个示例数组 nums 并调用 maxSubArray 函数，然后打印出最大子数组的和。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

int maxSubArray(std::vector<int>& nums) {
    int maxSum = nums[0];
    int currentMax = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        currentMax = std::max(nums[i], currentMax + nums[i]);
        maxSum = std::max(maxSum, currentMax);
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    std::cout << "Maximum Subarray Sum: " << maxSubArray(nums) << std::endl;
    return 0;
}

这段 C++代码实现了同样的功能。它定义了一个 maxSubArray 函数，该函数接受一个整数类型的 vector 引用 nums 并返回最大子数组的和。在 main 函数中，我们创建了一个示例 vector nums 并调用 maxSubArray 函数，然后输出最大子数组的和。这里使用了 <algorithm> 头文件中的 std::max 函数来简化代码。

Python 版本

def max_sub_array(nums):
    max_sum = current_max = nums[0]

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

    return max_sum

if __name__ == "__main__":
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print("Maximum Subarray Sum:", max_sub_array(nums))

这段 Python 代码定义了一个 max_sub_array 函数，它接受一个整数列表 nums 并返回最大子数组的和。在 if __name__ == "__main__": 块中，我们定义了一个示例列表 nums 并调用 max_sub_array 函数，然后打印出最大子数组的和。

Java 版本

public class Main {

    public static int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentMax = nums[0];

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

        return maxSum;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + maxSubArray(nums));
    }
}

这段 Java 代码实现了最大子数组和的功能。maxSubArray 方法接受一个整数数组 nums 并返回最大子数组的和。在 main 方法中，我们创建了一个示例数组 nums 并调用 maxSubArray 方法，然后输出最大子数组的和。Java 中的 Math.max 方法用于比较两个值并返回较大的一个。

Rust 版本

fn max_sub_array(nums: Vec<i32>) -> i32 {
    let mut max_sum = nums[0];
    let mut current_max = nums[0];

    for &num in nums.iter().skip(1) {
        current_max = std::cmp::max(num, current_max + num);
        max_sum = std::cmp::max(max_sum, current_max);
    }

    max_sum
}

fn main() {
    let nums = vec![-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("Maximum Subarray Sum: {}", max_sub_array(nums));
}

这段 Rust 代码定义了一个 max_sub_array 函数，它接受一个整数向量 nums 并返回最大子数组的和。在 main 函数中，我们创建了一个示例向量 nums 并调用 max_sub_array 函数，然后打印出最大子数组的和。Rust 的 std::cmp::max 函数用于比较两个值并返回较大的一个。

总结

上述解法采用了著名的动态规划方法来解决最大子数组和的问题，这种方法也被称为卡迪兰（Kadane's）算法。核心思想是遍历数组，同时计算到当前位置为止的最大子数组和。算法可以分为以下几个步骤：

初始化两个变量，maxSum 和 currentMax，分别用来存储迄今为止遇到的最大子数组和以及到当前位置为止的最大子数组和。这两个变量最初都被设置为数组的第一个元素。
从数组的第二个元素开始遍历，对于每个元素，更新 currentMax 的值。这个更新是基于一个判断：是选择当前元素作为新子数组的起点，还是将当前元素加到现有子数组和中。这可以通过比较 currentMax + nums[i] 和 nums[i] 的值来决定。
更新 maxSum 的值，如果 currentMax 的新值大于 maxSum，则 maxSum 应更新为 currentMax 的值。
遍历完成后，maxSum 将包含整个数组的最大子数组和。

这种方法的时间复杂度为 O(n)，因为它只需要遍历数组一次。空间复杂度为 O(1)，因为它只需要常数级别的额外空间。这种算法在各种编程语言中都很容易实现，如上所示的 Golang、C++、Python、Java 和 Rust 版本。

hot-100