最大子段和

作者:北京诚信汇发物流有限公司  来源:www.cxhfwL.com  发布时间:2017-09-07 13:12:52
最大子段和

给出一个数组,求其最大子数组和(要求最少取一个元素)

主要是用动态规划法,用dp(n)表示从0到n之间的最大子数组和。其状态转移方程为dp(n)=dp(n-1)<0?array[n] : dp(n-1)+array[n]

代码如下:

class Solution { public: int maxSubArray(vector& nums) { int res = numeric_limits::min(); int sum = 0; int size = nums.size(); for (int i = 0; i < size; i++) { if (sum > 0) sum += nums.at(i); else sum = nums.at(i); res = max(res, sum); } return res; } };

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:黄石SEO http://huangshi.4567w.com


上一篇:WPF 实现DataGrid行鼠标经过、点击时的背景、文字、行
下一篇:最后一页