item31,连续子数组的最大和

整型数组,元素有正数和负数。数组中一个或连续的多个整数组成一个子数组,求所有子数组中最大值。

===========

动态规划,

状态转移方程,max[].size = nums.size()

max[i]= max[i-1]+nums[i],if max[i-1]>0

nums[i],              if max[i-1]<=0

这样的max[]中存放就是由所有的子数组和,另外我们可以在产生每个子数组的时候,记住最大的那个数就可以了。

======================

代码:

int findGreatestSumOfSubArray(int *data,int length){
/**
f(i):
*/
if(data==nullptr || length<=){
return ;
}
int fi = data[];
int Greatest = data[];
for(int i = ;i<length;i++){
if(fi>){
fi = fi+data[i];
}else{
fi = data[i];
}
Greatest = fi>Greatest? fi:Greatest;
}
return Greatest;
}///end-function
上一篇:Python12/25--前端之BOM/DOM


下一篇:inux IO 内核参数调优 之 参数调节和场景分析