如何实现最大子数组和算法？

最大子数组和(Maximum Subarray Sum)问题是求一个数组中的最大子数组和。

我们可以使用动态规划实现最大子数组和算法:

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int maxSum = dp[0];

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

    return maxSum;
}

算法流程:

1. 初始化dp数组和maxSum。dp[i]表示以nums[i]结尾的最大子数组和,maxSum表示全局最大子数组和。
2. dp[0] = nums[0]。最大子数组和至少包含第一个数。
3. 对于其他位置i,dp[i]为两个值中的最大值:

• dp[i – 1] + nums[i]:将当前数添加到以前一个数结尾的最大子数组和。
• nums[i]:当前数单独作为最大子数组和。

1. maxSum为dp中的最大值,用来记录全局最大子数组和。
2. 重复步骤3和4,最终maxSum为最大子数组和,返回maxSum。

时间复杂度 O(n),空间复杂度 O(n)。

所以,最大子数组和的关键是:

1. 定义dp数组,dp[i]表示以nums[i]结尾的最大子数组和。maxSum记录全局最大子数组和。
2. dp[i]为两者中的最大值:dp[i – 1] + nums[i]或nums[i]。前者代表将当前数加入前面最大子数组和,后者代表当前数单独构成最大子数组和。
3. maxSum始终记录dp中的最大值,最终为最大子数组和。
4. 重复上述步骤计算dp数组,maxSum即为最终结果。