网站访问慢原因,网站服务器维护技术,大良网站建设价格,wordpress 中英插件题目链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 使用动态规划的方法进行解决#xff0c;我们创建一个dp表#xff0c;用来记录以该下标为结尾的最大子数组。然后每次存dp表的时候#xff0c;进行取最大值。最终返回最大值。 由…题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目解析 使用动态规划的方法进行解决我们创建一个dp表用来记录以该下标为结尾的最大子数组。然后每次存dp表的时候进行取最大值。最终返回最大值。 由于dp表存的是以当前下标为结尾的最大子数组和因此我们填表的时候需要判断如果当前下标对应的数组值与前一个位置的dp表所对应位置的和大于该位置对应的数组值那么该位置就为dp[i-1]nums[i-1]反之为nums[i-1]需要注意的是因为我们填dp表的第一个位置的时候会访问到-1下标的位置因此我们给dp表多开辟一个位置来解决这个问题 状态转移方程
由于dp表多开辟一个位置因此nums数组映射的时候需要-1
dp[i]max(dp[i-1]nums[i-1],nums[i-1]);
创建dp表
多创建一个位置来防止填写第一个位置的时候访问到-1下标。
vectorint dp(n1);
代码
class Solution
{
public:int maxSubArray(vectorint nums) {int nnums.size();// 创建dp表vectorint dp(n1);dp[0]0;int retINT_MIN;for(int i1;in1;i){// 求以i位置为结尾的最大数组和dp[i]max(dp[i-1]nums[i-1],nums[i-1]);// 记录最大和retmax(dp[i],ret);}// 返回最大和return ret;}
};
