leetcode-最大连续子数组的和-25-白红宇的个人博客

leetcode-最大连续子数组的和-25

发布日期：2021-05-04 18:21:45 浏览次数：21 分类：精选文章

本文共 427 字，大约阅读时间需要 1 分钟。

题目要求

求一个数组的最大连续子数组的和，数组中肯定有负数。

思路

采用动归的方式。

子问题：局部数字构成的数组，它的最大连续和

状态F（i）：前i个元素组成的数组，它的最大连续子序列的和

转移方程：F（i） = max（F（i-1）+a[i],a[i]）

图解

代码实现

class Solution {public:	int FindGreatestSumOfSubArray(vector
   
     array) {		if (array.empty())		{			return 0;		}		int ret = array[0];		for (int i = 1; i < array.size(); i++)		{			array[i] = max(array[i - 1] + array[i], array[i]);			ret = max(ret, array[i]);		}		return ret;	}};

上一篇：浅谈栈（Stack）实现

下一篇：leetcode-矩形覆盖-24

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章