什么网站用来做商城好,在网站上卖东西怎么做,在线作图软件,wordpress上传的文件在哪里一.题目要求
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。 子数组 是数组中的一个连续部分。
二.题目难度
中等
三.输入样例
示例 1#xff1a; 输入#xff1a;nu…一.题目要求
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。
二.题目难度
中等
三.输入样例
示例 1 输入nums [-2,1,-3,4,-1,2,1,-5,4] 输出6 解释连续子数组 [4,-1,2,1] 的和最大为 6 。
示例 2 输入nums [1] 输出1
示例 3 输入nums [5,4,-1,7,8] 输出23
提示 1 nums.length 105 -104 nums[i] 104
进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
四.解题思路 d p [ i ] m a x ( d p [ i − 1 ] n u m s [ i ] , n u m s [ i ] ) dp[i] max (dp[i - 1] nums[i], nums[i]) dp[i]max(dp[i−1]nums[i],nums[i]) d p [ i ] 表示以 i 位置为结尾的连续子数组最大和 dp[i]表示以i位置为结尾的连续子数组最大和 dp[i]表示以i位置为结尾的连续子数组最大和
由于当前状态只受前一个状态的影响故可以用滚动数组进行优化
五.代码实现
class Solution {
public:int maxSubArray(vectorint nums) {int n nums.size();int ans nums[0];int pre nums[0];for(int i 1; i n; i){pre max(pre nums[i], nums[i]);ans max(pre, ans);}return ans;}
};六.题目总结
–
