时间轴

2025-12-02

init

题目：

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]重新开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
        }
};