首页 > 其他 > 详细

leetcode 53最大子序和

时间:2019-02-20 23:04:17      阅读:180      评论:0      收藏:0      [点我收藏+]

DP题,DP数组dp[i]为以第i个项结尾的子序列最大和。

如果一个dp[i-1]>0那么当前的nums[i]可以将前一个子序列和加上,否则为负值加上只能减小将dp[i]赋值为nums[i],然后再从中筛选最大的子序列和

DP推导式,max_value=max(dp[i],max_value) 

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==1)return nums[0];
        if(nums.size()==0)return 0;
        int a[100000]={0};
        a[0]=nums[0];
        int max_=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(a[i-1]>0)
            a[i]=a[i-1]+nums[i];
            else
            a[i]=nums[i];
            max_=max(max_,a[i]);
        }
        return max_;
    }
};

 

leetcode 53最大子序和

原文:https://www.cnblogs.com/biubiuWham/p/10409694.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!