建站宝盒的设置,菜鸟制作个人网站网页实例,网站提示危险怎么办,杭州下沙开发区建设局网站题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢#…题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组返回它的最大连续子序列的和你会不会被他忽悠住(子向量的长度至少是1)
解题思路
如果我们有个序列{1,-2,3},显然最大子序列是{3},如果我们在这个序列后面再加入一个数t我们怎么去求加入一个数之后新的序列的连续子序列{1-23t}的最大和 设以t为序列尾的最大子序列和为sum,则我们可以很直观地看出summax{3t,t}这样理解起来很简单因为3就在t前面而我们已经知道以3为结尾的最大连续子序列和就是3这个3就是t绕不过去的一个坑。 知道这个关系后我们就可以由题目推出这样一个式子 设F[n]为下标为n结尾的连续子序列最大和数组名为num 推出:F[n]max{F[n-1]num[n]}
代码实现
class Solution {
public:int GetMax(int a,int b){return ab?a:b;}int FindGreatestSumOfSubArray(vectorint array) {if(array.empty())return 0;int sum array[0];int max array[0];for(int i 1; i array.size();i){max GetMax(maxarray[i],array[i]);sum GetMax(sum,max);}return sum;}
};
