给定一个数组，找出这个数组最大连续子数组的和

110 阅读 0 评论 73 点赞

我是靠谱客的博主老迟到小蝴蝶，这篇文章主要介绍给定一个数组，找出这个数组最大连续子数组的和，现在分享给大家，希望可以做个参考。

将这个连续子数组分为两部分，一个是前缀，一个是后一个元素，要使这个连续子数组最大，那么它的前缀肯定不能为负，不然这个前缀对即将加上的值就无意义，用一个max记录最大值，每次当前缀加上后一个元素的时候判断和是否大于max，大于则更新max，再判断和是否小于0，小于0则将前缀更新为0，继续加下一个元素，依次类推，直到数组末尾，max即为最大子数组和。代码如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){
            return 0;
        }
        int max = array[0];
        int current = array[0]<0?0:array[0];
        for(int i=1;i<array.length;i++){
            current += array[i];
            if(current>max){
                max = current;
            }else if(current<0){
                current = 0;
            }
        }
        return max;
    }
}