53. 最大子序和

1、题目描述

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

2、思路

dp[i] 表示以nums[i]结尾的连续子数组的最大和;
那么若 dp[i-1] >= 0; dp[i] = dp[i-1] + nums[i]
若dp[i-1] < 0; 则dp[i] = nums[i];

3、代码实现(C++)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) {
            return 0;
        }
        int res = 0;
        vector<int> dp(len);
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            res = max(dp[i], res);
        }
        return res;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 53. 最大子序和 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其...
    傅晨明阅读 237评论 0 0
  • 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输...
    薄荷糖的味道_fb40阅读 167评论 0 0
  • 题目描述(简单难度) 给一个数组,找出一个连续的子数组,长度任意,和最大。 解法一 动态规划思路一 用一个二维数...
    windliang阅读 233评论 0 0
  • 更多精彩内容,请关注【力扣简单题】。 题目 难度:★★☆☆☆类型:数组 给定一个整数数组 nums ,找到一个具有...
    玖月晴阅读 2,340评论 0 0
  • 题目描述: 给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 ...
    小刘一定要努力阅读 179评论 0 0