当前位置:   article > 正文

LeetCode 53.最大子数组和(dp)

LeetCode 53.最大子数组和(dp)

给你一个整数数组 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

这道题是一道动态规划,我们通过比较nums【i】与dp【i-1】+ nums【i】来判断这个位置的最大值,代码如下:

  1. class Solution {
  2. public:
  3. int maxSubArray(vector<int>& nums) {
  4. int n = nums.size(),ans = -10005;
  5. if(n == 1) return nums[0];
  6. vector<int> dp(n,0);
  7. dp[0] = nums[0];
  8. for(int i=1;i<n;i++){
  9. dp[i] = max(nums[i],dp[i-1]+nums[i]);
  10. }
  11. for(int i=0;i<n;i++){
  12. ans = max(dp[i],ans);
  13. }
  14. return ans;
  15. }
  16. };

加油

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/786164
推荐阅读
相关标签
  

闽ICP备14008679号