最大子串

连续子数组的最大和

http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484

需要两个变量,res用来储存目前已知最大的子串的和,max用来存储累加的和,后者会随着循环的推进不断更新。
如果累加的和为负数,说明累加的值不会对后面的和有利,就会把累加的和丢弃;然后把最新的一个值赋值给max(这个值有没有用要下轮循环才知道)。
如果累加的和大于0,说明前面的累加对后面的子串有帮助,就会继续把当前循环的值也加入到前面的累加的和中。
每次进行完上面的步骤都会有一次判断,看看max和res那个更大,如果max大于res,就更新res。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0){
return 0;
}
int res=array[0],max=array[0];
for(int i=1;i<array.length;i++){
if(max>=0){
max=max+array[i];
}else{
max=array[i];
}
if(max>res){
res=max;
}
}
return res;
}
}

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务