Fork me on GitHub

求解连续子数组的最大和

发表于

背景

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

  • 例子说明：例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为｛3, 10, -4, 7, 2}。因此输出为该子数组的和18 。

    解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static int findBiggestSumOfSubArray(int[] array){
        if (array == null || array.length <= 0){
            return Integer.MIN_VALUE;
        }
        // 记录最大的子数组和，开始时是最小的整数
        int max = Integer.MIN_VALUE;
        //当前的和
        int currentSum = 0;
        for (int per:array) {
            // 如果当前和小于等于0，重置当前和
            if (currentSum <= 0){
                currentSum = per;
            }else {
                // 如果当前和大于0，累加当前和
                currentSum = currentSum + per;
            }
            // 记录当前的最大子数组和
            if (currentSum > max){
                max = currentSum;
            }
        }
        return max;
    }
1
2
3
4
5
6
7
8
public static void main(String[] args){
        int[] data = {1, -2, 3, 10, -4, 7, 2, -5};
        int[] data2 = {-2, -8, -1, -5, -9};
        int[] data3 = {2, 8, 1, 5, 9};
        System.out.println(findBiggestSumOfSubArray(data));
        System.out.println(findBiggestSumOfSubArray(data2));
        System.out.println(findBiggestSumOfSubArray(data3));
}

运行结果：

1
2
3
4
"D:\IntelliJ IDEA 2019.3.1\jbr\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2019.3.1\lib\idea_rt.jar=63150:D:\IntelliJ IDEA 2019.3.1\bin" -Dfile.encoding=UTF-8 -classpath D:\IdeaProject\Reflect\out\production\Reflect com.ai.ReflectTest
18
-1
25

连续子数组的最大和