题目

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

举例

输入：2, -3, 4, 5, -9

输出：9

和最大的连续子数组是 {4, 5}，结果就是9。

贪心算法

我们先假设和最大连续子数组是从第一个数开始的。初始化和为0。第一步是加上数字2，此时和为2。第二步加上数字-3，此时和为-1。那么问题来了，我们到底要不要加上数字-3呢？分析过程如下：

  1. 加上-3。此时的和为-1。
  2. 不加-3。也就是意味当前连续子数组就终结于-3之前的数字，下一个连续子数组的和初始化为0，再加上第一个数字-3，和为-3。

由上述分析可知，加上-3，此时累加的子数组和是-1；不加-3，此时累加的子数组和是-3。-1大于-3，为了后续的累加和更大，所以选择加上-3。

接下来，第三步要不要加上数字4，我们依据上面的决策流程继续分析。当加上数字4，此时累加和为3；不加上数字4，意味着当前连续子数组终结于数字4之前，此时的累加和初始化为0，加上数字4后和等于4。显而易见，4大于3，所以我们选择抛弃前面的累加和，由数字4继续开始。

后续步骤省略，总结一番。当我们遍历数组时，对于每个数字，要么与前面的子数组累加，要么作为新子数组的起点，如果累加之后的子数组和小于当前数字，我们就选择抛弃前面的累加和，将当前数字作为新子数组的起点。整个过程可以用表格总结如下：

步骤 操作 累加的子数组和 最大的子数组和
1 加2 2 2
2 加-3 -1 2
3 抛弃累加的和-1，加4 4 4
4 加5 9 9
5 加-9 0 9

代码

根据题目要求，我们只需要求出连续子数组的最大和，如果面试官还要求找到连续子数组的起点与终点下标，那么最终的java代码如下：

public class Main {

    public static int maxSubArray(int[] nums) {
        // 处理边界
        if (nums == null || nums.length < 1) {
            return 0;
        }
        // 初始化
        int sum = 0;
        int max = nums[0];
        // 记录起点和终点需要三个指针
        int left = 0;
        int right = 0;
        int temp = 0;
        // 遍历
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum < nums[i]) {
                sum = nums[i];
                temp = i;
            }
            if (sum > max) {
                max = sum;
                left = temp;
                right = i;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, -3, 4, 5, -9};
        int[] arr2 = new int[]{2, -2, 4, 5, -9};
        int[] arr3 = new int[]{-2, -3, -4, -5, -9};
        System.out.println(maxSubArray(arr1));
        System.out.println(maxSubArray(arr2));
        System.out.println(maxSubArray(arr3));
    }
}

打印输出：

9
9
-2

复杂度

时间复杂度：O(n) 只遍历一次数组

空间复杂度：O(1) 只使用常数个空间

动态规划

f(i)=max{f(i−1) + nums[i], nums[i]}

代码

public class Main {

    public static int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int sum = 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            sum = Math.max(sum + nums[i], nums[i]);
            max = Math.max(sum, max);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[] { 2, -3, 4, 5, -9 };
        int[] arr2 = new int[] { 2, -2, 4, 5, -9 };
        int[] arr3 = new int[] { -2, -3, -4, -5, -9 };
        System.out.println(maxSubArray(arr1));
        System.out.println(maxSubArray(arr2));
        System.out.println(maxSubArray(arr3));
    }
}

复杂度

时间复杂度：O(n) 只遍历一次数组

空间复杂度：O(1) 只使用常数个空间