LeetCode 力扣 热题 100道（十八）最大子数组和（C++）
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int currentSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
};
最终返回 maxSum = 6。
-
currentSum：
currentSum表示当前以nums[i]结尾的子数组的和。我们会选择当前的nums[i]单独作为一个新的子数组，或者将其加入到currentSum中，取决于哪种选择能使和更大。
-
maxSum：
maxSum是记录到当前为止的最大子数组和。我们在每一步更新currentSum后，检查是否需要更新maxSum。
-
动态规划的递推关系：
currentSum = max(nums[i], currentSum + nums[i])：如果currentSum + nums[i]更大，就继续扩大当前子数组；否则，从当前位置i开始新一个子数组。maxSum = max(maxSum, currentSum)：更新全局的最大子数组和。
-
假设
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]： - 初始化时，
currentSum = -2和maxSum = -2。 - 第2个元素：
currentSum = max(1, -2 + 1) = 1，maxSum = max(-2, 1) = 1。 - 第3个元素：
currentSum = max(-3, 1 + (-3)) = -2，maxSum = max(1, -2) = 1。 - 第4个元素：
currentSum = max(4, -2 + 4) = 4，maxSum = max(1, 4) = 4。 - 第5个元素：
currentSum = max(-1, 4 + (-1)) = 3，maxSum = max(4, 3) = 4。 - 第6个元素：
currentSum = max(2, 3 + 2) = 5，maxSum = max(4, 5) = 5。 - 第7个元素：
currentSum = max(1, 5 + 1) = 6，maxSum = max(5, 6) = 6。 - 第8个元素：
currentSum = max(-5, 6 + (-5)) = 1，maxSum = max(6, 1) = 6。 - 第9个元素：
currentSum = max(4, 1 + 4) = 5，maxSum = max(6, 5) = 6。
原文地址：https://blog.csdn.net/weixin_64593595/article/details/144435898
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！