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