此题笔者想出两种 解题模式
第一种暴力解决方法,直接遍历数组array 依次计算a[1]的值 a[1]+a[2]的值 a[1]+a[2]+a[3]的值
依次类推求出 各种连续子数组的值,然后依次与max值比较。
第二种采用动态规划的思想
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { int cursum=0; //cursum为截止到当前数组序号前 连续字数组的最大值 int ret=array[0];//ret为当前数组的第一个字符串 for(int i=0;i<array.size();i++) //遍历数组array { if(cursum<=0) cursum=array[i]; //当前数组序号前最大值小于零,则加上当前序号最大值不超过当前值 else cursum+=array[i]; ret=max(ret,cursum);//不断将cursum的值进行比较,调出大者放入ret; } return ret; } };
最后
以上就是发嗲身影最近收集整理的关于leetcode剑指offer JZ42 连续子数组的最大和的全部内容,更多相关leetcode剑指offer内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复