牛客网刷到了连续子数组的最大和的题,学习完以后记录一下两个解法。

连续子数组的最大和

题目描述

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).

解题思路

算法时间复杂度O（n）

利用array[i]记录累计较大值值，利用max与array与之比较，使得max始终记录最大值，最后返回max。

题解代码

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array.length == 0){return 0;}
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < array.length; i++){
            array[i] = Math.max(array[i],array[i-1]+array[i]);
            max = Math.max(array[i],max);
        }
        return max;
    }
}

其他解法

思路：

通过判断i前的累积是否大于0，来判断是否继续进行累加。

使sum 记录累加值，maxvalue 记录最大值，两者比较，使maxvalue 始终取最大值。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
    int sum=0;
    int maxvalue=array[0];
    for(int i=0;i<array.length;i++){
        if(sum<=0){
          sum=array[i];  
        }else{sum=sum+array[i];}
         maxvalue=Math.max(maxvalue,sum);
    }
        return maxvalue;
    }
}

参考

牛客网