做网站的文章,旺道seo系统,枣庄建设局网站,网站开发er图题目来源#xff1a; leetcode题目#xff0c;网址#xff1a;53. 最大子数组和 - 力扣#xff08;LeetCode#xff09;
解题思路#xff1a; 动态规划#xff0c;假设以第 i 个元素为结尾的最大子数组和为 dp[i]#xff0c;则 dp[i]max(dp[i-1]nums[i],nums[i])。最…题目来源 leetcode题目网址53. 最大子数组和 - 力扣LeetCode
解题思路 动态规划假设以第 i 个元素为结尾的最大子数组和为 dp[i]则 dp[i]max(dp[i-1]nums[i],nums[i])。最后返回其中最大值即可。
解题代码
class Solution {
public:int maxSubArray(vectorint nums) {int maxSumnums[0];int prenums[0];for(int i1;inums.size();i){premax(prenums[i],nums[i]);maxSummax(pre,maxSum);}return maxSum;}
};
总结 官方题解给出了两种解法。第一种是动态规划。第二种是分治分治法利用递归将原来的数组切割为一个一个的小数组在小数组内获得问题的解然后不断合并小数组在此期间根据小数组的信息得到大数组的相应信息。最后所有的小数组被合并为一个时得到的数据即为所求。
