时间轴

2025-12-02

init

题目：

P53 最大子数组和

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

动态规划思想，dp[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;
	}
};