[30] 连续子数组的最大和(简单)
[30] 连续子数组的最大和(简单)

题目描述

输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)
输入:[1,-2,3,10,-4,7,2,-5]
返回值:18
说明:输入的数组为{1,-2,3,10,4,7,2,5},和最大的子数组为{3,10,4,7,2},因此输出为该子数组的和 18

解题思路

暴力法

从头开始拿数,将本次拿到的数依次与后面的数字进行求和比对,谁大谁就存起来,最后返回的结果一定是最大的。
/**
 * 暴力法
 * T(n^2) S(1)
 */
public int FindGreatestSumOfSubArray(final int[] array) {
    int result = array[0];
    for (int i = 0; i < array.length; i++) {
        int max = result;
        int sum = 0;
        for (int j = i; j < array.length; j++) {
            sum += array[j];
            max = Math.max(sum, max);
        }
        result = Math.max(result, max);
    }
    return result;
}

动态规划 1

定义一个比输入数组长度大 1 的临时数组,临时数组中每个元素保存的是以上一个元素结尾时最大子数组之和,如 temp[i] 等于以 temp[i - 1] 结尾的最大子数组之和:
输入数组:1, -2, 3, 10, -4, 7, 2, -5
临时数组:0, 1, -1, 3, 13, 9, 16, 18, 13
array[i - 1]temp[i - 1] + array[i - 1] 作比较 ,谁大谁就赋值给 temp[i],用于保存以第 i-1 个元素结尾的最大子数组之和,作为下次运算依据。
遍历过程:
i: 1     temp[i]: 1      result: 1
i: 2     temp[i]: -1     result: 1
i: 3     temp[i]: 3      result: 3
i: 4     temp[i]: 13     result: 13
i: 5     temp[i]: 9      result: 13
i: 6     temp[i]: 16     result: 16
i: 7     temp[i]: 18     result: 18
i: 8     temp[i]: 13     result: 18
/**
 * 动态规划 1
 * T(n) S(n)
 */
public int FindGreatestSumOfSubArray(final int[] array) {
    // 临时数组
    int[] temp = new int[array.length + 1];
    temp[0] = 0;
    // 最大结果
    int result = array[0];
    for (int i = 1; i <= array.length; i++) {
        // 输入数组的上一个值与输入数组的上一个值和临时数组的上一个值之和作比较,
        // 谁大谁就赋值给临时数组的当前值
        temp[i] = Math.max(array[i-1], temp[i - 1] + array[i - 1]);
        // 记录临时数组当前值是否为最大结果
        result = Math.max(result, temp[i]);
    }
    return result;
}

动态规划 2

沿用上一解法的思想,这次仅使用一个变量来记录以上一个元素结尾的最大子序列之和,每次迭代时将暂时子序列之和与当前元素求和,如果小于 0 则说明当前元素为负数且加上前一个最大子序列之和都不大于 0,以当前元素结尾的对最大子序列应当不做贡献,所以会被丢弃,重新开始记录暂时最大子序列。
如果输入数组中全为负数的情况出现,比较出来的结果会为 0,此时就选数组中最大的一个元素返回即可。
/**
 * 动态规划 2
 * T(n) S(1)
 */
public static int FindGreatestSumOfSubArray(final int[] array) {
    // 当输入数组的元素全为负数时,需要返回数组中最大的元素
    int max = array[0];
    // 最大子序列之和
    int result = array[0];
    // 暂时的最大子序列之和
    int temp = 0;
    for (int i = 0; i < array.length; i++) {
        // 将暂时最大子序列之和与当前元素求和
        temp += array[i];
        // 如果小于 0 则说明以当前元素结尾的对最大子序列不做贡献
        if (temp < 0) {
            // 废弃以当前元素结尾的子序列,重置暂时最大子序列之和,重新寻找子序列
            temp = 0;
        }
        // 将暂时子序列与之作比较,谁大谁就作为目前的最大子序列
        result = Math.max(result, temp);
        // 每次迭代顺便比较记录一下输入数组中的最大元素
        max = Math.max(max, array[i]);
    }
    // result = 0 说明当前数全为负数,则需要返回输入数组中最大的一个元素
    return result != 0 ? result : max;
}