文章目录
- 1.题目
- 示例
- 提示
- 2.解答思路
- 3.实现代码
- 结果
- 4.总结
1.题目
给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例
提示
2.解答思路
起初思路暴力求解,两层for循环,但超出时间限制。
查看其他题解,学习以下动态规划算法。
关于动态规划算法,后续会出一篇文章详细解释。
此处简述:
动态规划的核心思想是将原始问题分解为更小的子问题,并通过求解子问题的解来推导出原始问题的解。避免重复计算,提高算法的效率。
3.实现代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum=nums[0];
int n=nums.size();
int sum=nums[0];//记录当下的和
for(size_t i=1;i<n;++i){
sum += nums[i];
sum = max(sum,nums[i]);
/*
将当下及之前元素的和max和单个元素进行比较nums[i],求最大值
若当下的和 大于 单个元素,则加和运算
若当下的和 小于 单个元素,则将单个元素的值赋给max,
以便后续继续求解*/
maxSum=max(sum,maxSum);
}
return maxSum;
}
};
结果
暴力求解一直超时。
动态规划算法将时间复杂度降到了O(n),通过。
4.总结
前两天感冒突然严重+家中亲人走访,学习时间减少,今天病情好转,后续会继续更新学习。
自信,坚持,upup~