数据结构与算法

最大（小）子段和

略

输入一个整型数组,数组中有正数也有负数,这个数组中一个或者连续多个整数组成的子数组,求其子数组的最大(最小)值.要求时间复杂度为O(n).例如数组{1,-2,3,10,-4,7,2,-5},它的最大子段为{3,10,-4,7,2},和为18.

分析

很多人直观的想法是枚举该数组的所有子数组的和,一个长度为n的数组,一共有n(n-1)/2个子数组,计算所有和时间复杂度至少为O(n²),不符合题目,所以要用另外一个方法来解.

我们可以从数组开头来累加每个元素,例如{1}最大为1,{1,-2}最大为1,{1,-2,3}最大为3,此时因为加上{1,-2}这两条数据后子段不加反减,所以需要排除掉{1,-2},从{3}开始累加,{3,10}最大13,{3,10,-4}最大为13,{3,10,-4,7}最大为16,{3,10,-4,7,2}最大为18,{3,10,-4,7,2,-5}最大为18,此时数组完全都被遍历,所以排除掉{-5}.此时得到最大子段和为18.

步骤 操作 叠加的子段和 最大子段和
1 加1 1 1
2 加-2 -1 1
3 放弃前面的和-1加3 3 3
4 加10 13 13
5 加-4 9 13
6 加7 16 16
7 加2 18 18
8 加-5 13 18

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int findGreatestSumOfArray(int[] arr) {

        int len = arr.length;
        int sum = 0;
        int maxSum = 0;

        if (arr.length <= 0 || arr == null) {//如果长度为0或者arr为空输出为0
            return 0;
        }

        for (int i = 0; i < len; i++) {
            if (sum <= 0) sum = arr[i];
            else sum += arr[i];//累加子段和
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return maxSum;
    }

总结

跳出组合的圈子,对于大数据不要尝试使用枚举,注意时间复杂度.