题解 | 连续子数组的最大和

1、解题思路

1. 动态规划：定义 dp[i] 为以 array[i] 结尾的子数组的最大和。状态转移方程： 对于每个 i，如果 dp[i-1] 为正，则 dp[i] = dp[i-1] + array[i]。否则，dp[i] = array[i]（即重新开始一个新的子数组）。初始条件： dp[0] = array[0]。结果： max_sum 是所有 dp[i] 中的最大值。
2. 优化（Kadane算法）：使用一个变量 current_sum 代替 dp 数组，记录当前子数组的和。另一个变量 max_sum 记录全局最大子数组和。遍历数组时，更新 current_sum 和 max_sum。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型
     */
    int FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        if (array.empty()) {
            return 0;
        }

        int current_sum = array[0];
        int max_sum = array[0];
        for (int i = 1; i < array.size(); ++i) {
            current_sum = max(array[i], current_sum + array[i]);
            max_sum = max(max_sum, current_sum);
        }
        
        return max_sum;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型
     */
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        if (array.length == 0) return 0;
        int current_sum = array[0];
        int max_sum = array[0];
        for (int i = 1; i < array.length; ++i) {
            current_sum = Math.max(array[i], current_sum + array[i]);
            max_sum = Math.max(max_sum, current_sum);
        }
        return max_sum;
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        if not array:
            return 0
        current_sum = max_sum = array[0]
        for num in array[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)
        return max_sum

3、复杂度分析

• 时间复杂度：O(n)，仅需遍历数组一次。
• 空间复杂度：O(1)，仅使用常数个额外变量。