面试经典150题 P53 最大子数组和

---

时间轴

时间轴

2025-12-02

init

动态规划, Kadane算法

---

题目：

P53 最大子数组和

https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-interview-150

动态规划思想，dp[i]表示以 nums[i]结尾的最大子数组的和，那么

$$dp[i] = max{ dp[i-1]+nums[i], nums[i]}$$

即如果之前的子数组和加上 nums[i]比 nums[i]还小，那干脆从 nums[i]重新开始。

#include <vector>
using std::vector;

class Solution {
    public:
	int maxSubArray(vector<int> &nums)
	{
		int i, n = nums.size();
		int max_sum = nums[0];
		vector<int> dp(n);
		dp[0] = nums[0];
		for (i = 1; i < n; i++) {
			dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
			max_sum = std::max(max_sum, dp[i]);
		}
		return max_sum;
	}
};

leetcode hot 100 rewrite

#include <vector>
#include <climits>

using std::vector;

class Solution {
    public:
        int maxSubArray(vector<int> &nums)
        {
                int i, n = nums.size();

                if(n == 0) return 0;

                int max_sum = nums[0];

                // 动态规划
                // dp[i]表示以nums[i]结尾的最大子数组和
                // dp[i] = max{dp[i-1]+nums[i], nums[i]}
                // 即如果之前的子数组和加上 nums[i]比 nums[i]还小，那干脆从 nums[i]重新开始。

                vector<int> dp(n, 0);

                dp[0] = nums[i];

                for (i = 1; i < n; i++) {
                        dp[i] = std::max(dp[i - 1] + nums[i], nums[i]);
                        max_sum = std::max(max_sum, dp[i]);
                }

                return max_sum;
        }
};