题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

题目分析

动态规划

动态规划，设 dp[i] 表示以 i 为结尾的子数组的最大和
则有 dp[i] = Math.max(dp[i – 1] + nums[i], nums[i])
进一步会发现 dp 数组的每个元素都只使用一次，因此可以简化为单个变量
时间复杂度 O(n)，空间复杂度 O(1)

递归分治

把数组从中间一分为二：左区间 left、右区间 right
设 maxSum 为子区间最大和，maxLSum 为左边界最大区间和，maxRSum 为右边界最大区间和，sum 为区间和。
则有
– maxSum = max{left.maxSum，right.maxSum，left.maxRSum + right.maxLSum}
– maxRSum = max{right.maxRSum, left.maxRSum + right.sum}
– maxLSum = max{left.maxLSum, left.sum + right.maxLSum}

因此可以直接递归来解决，递归的出口就是区间内只剩一个数字。
时间复杂度 O(n)

Java

public int maxSubArray1(int[] nums) {
    int dp = nums[0];
    int ans = nums[0];
    for (int i = 1; i < nums.length; i++) {
        dp = Math.max(dp + nums[i], nums[i]);
        ans = Math.max(dp, ans);
    }
    return ans;
}


private class Node {
    int start, end;
    int sum; // 区间和
    int maxSum, maxLSum, maxRSum;// 子区间最大和、左边界最大区间和、右边界最大区间和

    public Node(int start, int end) {
        // 前闭后闭
        this.start = start;
        this.end = end;
    }

    public void calculate(int[] nums) {
        if (start == end) {
            sum = nums[start];
            maxSum = nums[start];
            maxLSum = nums[start];
            maxRSum = nums[start];
            return;
        }

        int mid = (start + end) / 2;
        Node left = new Node(start, mid);
        Node right = new Node(mid + 1, end);
        left.calculate(nums);
        right.calculate(nums);

        sum = left.sum + right.sum;

        maxSum = Math.max(left.maxSum, right.maxSum);
        maxSum = Math.max(maxSum, left.maxRSum + right.maxLSum);

        maxLSum = Math.max(left.maxLSum, left.sum + right.maxLSum);
        maxRSum = Math.max(right.maxRSum, right.sum + left.maxRSum);
    }
}

public int maxSubArray2(int[] nums) {
    Node node = new Node(0, nums.length - 1);
    node.calculate(nums);
    return node.maxSum;
}

Kotlin

fun maxSubArray(nums: IntArray): Int {
    var dp = nums[0]
    var ans = nums[0]
    for (i in 1 until nums.size) {
        dp = max(nums[i], dp + nums[i])
        ans = max(ans, dp)
    }
    return ans
}