代码天涯路

53. 最大子数组和(Maximum Subarray)E

英文题目

  • Given an integer array nums, find the

  • subarray

  • Example 1:

  • Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

  • Example 2:

  • Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

  • Example 3:

  • Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

  • Constraints:

    • 1 <= nums.length <= 10^5
    • -10^4 <= nums[i] <= 10^4

  • Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

中文题目

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

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

  • 示例 1：

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

  • 示例 2：

  • 输入：nums = [1]
输出：1

  • 示例 3：

  • 输入：nums = [5,4,-1,7,8]
输出：23

  • 提示：

    • 1 <= nums.length <= 10^5
    • -10^4 <= nums[i] <= 10^4

  • 进阶： 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

暴力法

  • 采用双层循环，第一层循环是遍历数组的开始点，第二层循环是遍历数组的结束点，暴力得出所有连续子数组，然后计算其和，取最大值

  • 时间复杂度O(n^2)，空间复杂度O(1)

    # python: 会超时
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = float('-inf')
        for begin in range(len(nums)):
            sum = 0
            for end in range(begin, len(nums)):
                sum += nums[end]
                res = max(res, sum)
        return res

动态规划

  • 1.令 dp[i] 表示以 nums[i] 作为末尾的连续序列的最大和（dp[i]要求是必须以 nums[i] 结尾的连续序列）

  • 2.有两种情况：

    • 1.序列只有一个元素，以 nums[i] 开始，nums[i] 结尾，此时最大和即 nums[i] 本身
    • 2.序列有多个元素，以 nums[p] 开始 (p<i)，nums[i] 结尾，此时最大和是 dp[i-1]+nums[i] = nums[p]+...+nums[i-1]+nums[i]

  • 得状态转移方程：dp[i]=max{nums[i]，dp[i-1]+nums[i]}

  • 边界：dp[0]=nums[0]

  • 从小到大枚举i，即可得到整个dp数组，然后遍历dp找到最大值

  • 时间复杂度O(n)，空间复杂度视dp数组为O(n)或O(1)

    # python: 时间 152 ms, 击败 60.66%; 内存 30.2 MB, 击败 51.13%
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)

    // c++: 时间 96 ms, 击败 44.33%; 内存 68.8 MB, 击败 12.12%
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

    // java: 时间 3 ms, 击败 7%; 内存 56.1 MB, 击败 45.79%
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        }
        return max(dp);
    }

    private int max(int[] nums) {
        int res = Integer.MIN_VALUE;
        for (int x: nums) {
            res = Math.max(res, x);
        }
        return res;
    }
}

    // go: 时间 100 ms, 击败 41.10%; 内存 8.9 MB, 击败 12.55%
func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = maxInt(dp[i-1] + nums[i], nums[i])
    }
    return maxSlice(dp)
}

func maxInt(a, b int) int {
    if a > b {
        return a;
    }
    return b;
}

func maxSlice(nums []int) int {
    res := nums[0]
    for _, num := range nums {
        if res < num {
            res = num
        }
    }
    return res
}

    // Javascript: 时间 84 ms, 击败 57.47%; 内存 50.46 MB, 击败 25.41%
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let dp = new Array(nums.length).fill(0);
    dp[0] = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
    }
    return Math.max(...dp);
};

  • 因dp[i]仅与dp[i-1]相关，可只用一变量dp来保存，把空间复杂度降低到O(1)

    # python: 时间 168 ms, 击败 41.57%; 内存 30.58 MB, 击败 7.92%
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = res = nums[0]
        for i in range(1, len(nums)):
            dp = max(dp + nums[i], nums[i])
            res = max(res, dp)
        return res

    // c++: 时间 72 ms, 击败 98.20%; 内存 66.1 MB, 击败 76.44%
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0], res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp = max(dp + nums[i], nums[i]);
            res = max(res, dp);
        }
        return res;
    }
};

    // java: 时间 1 ms, 击败 100%; 内存 56.5 MB, 击败 28.22%
class Solution {
    public int maxSubArray(int[] nums) {
        int dp = nums[0], res = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            dp = Math.max(dp + nums[i], nums[i]);
            res = Math.max(res, dp);
        }
        return res;
    }
}

    // go: 时间 100 ms, 击败 41.10%; 内存 8.6 MB, 击败 74.33%
func maxSubArray(nums []int) int {
    dp, res := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        dp = maxInt(dp + nums[i], nums[i])
        res = maxInt(res, dp)
    }
    return res
}

func maxInt(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}

    // javascript: 时间 68 ms, 击败 98.2%; 内存 49.2 MB, 击败 65.62%
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let dp = nums[0], res = nums[0];
    for (let i = 1; i < nums.length; ++i) {
        dp = Math.max(dp + nums[i], nums[i]);
        res = Math.max(res, dp);
    }
    return res;
};

分治法

  • 参考：官方题解open in new window

  • 本质是利用了二叉树的后序遍历，类似于归并排序，对于每一个数组块，计算如下四个量：

    • iSum：[l, r] 的区间和，即所有元素加和
      • iSum 等于左右子区间 iSum 加和
    • lSum：[l, r] 内以 l 为左端点的最大子数组和
      • 两种可能取最大：
        • 要么等于「左子区间」的 lSum
        • 要么等于「左子区间」的 iSum 加上「右子区间」的 lSum
    • rSum：[l, r] 内以 r 为右端点的最大子数组和
      • 两种可能取最大：
        • 要么等于「右子区间」的 rSum
        • 要么等于「右子区间」的 iSum 加上「左子区间」的 rSum
    • mSum：[l, r] 内的最大子数组和(m 是 middle的意思)
      • 三种可能取最大：
        • 若不跨越区间，可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个
        • 若跨越两个区间，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和

  • 上面的几种可能性，牢记这个是连续子数组，且以左中右为端点，则可记住所有可能性

  • 最终mSum即为所求

  • 优势：

    • 该方法的空间复杂度和代码均比动态规划复杂，但它的意义在于，可用于解决任意子区间的问题，在大规模查询情况下占优

  • 时间复杂度：O(n)，可把递归的过程看作是二叉树的后续遍历，则二叉树的深度的渐进上界是O(log n)，这里总时间相当于遍历这颗二叉树的所有结点，估总时间的渐进上界是 ，故渐进时间复杂度是O(n)

  • 空间复杂度：O(log n)，因为递归使用O(log n)的栈空间

    # python: 时间 764 ms, 击败 5.7%; 内存 31.1 MB, 击败 20.12%
class Status:
    def __init__(self, iSum: int, lSum: int, rSum: int, mSum: int):
        self.iSum = iSum
        self.lSum = lSum
        self.rSum = rSum
        self.mSum = mSum

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        return self.get(nums, 0, len(nums)-1).mSum
    
    def get(self, nums: List[int], left: int, right: int) -> Status:
        if left == right:
            return Status(nums[left], nums[left], nums[left], nums[left])
        mid = left + (right - left) // 2
        lSub = self.get(nums, left, mid);
        rSub = self.get(nums, mid+1, right);
        return self.pushUp(lSub, rSub)
    
    def pushUp(self, left: Status, right: Status) -> Status:
        iSum = left.iSum + right.iSum
        lSum = max(left.lSum, left.iSum + right.lSum);
        rSum = max(left.rSum + right.iSum, right.rSum);
        mSum = max(left.mSum, right.mSum, left.rSum + right.lSum);
        return Status(iSum, lSum, rSum, mSum);

    // c++: 时间 108 ms, 击败 20.53%; 内存 66.1 MB, 击败 88.51%
class Solution {
public:
    struct Status {
        int iSum, lSum, rSum, mSum;
    };

    Status pushUp(Status left, Status right) {
        int iSum = left.iSum + right.iSum;
        int lSum = max(left.lSum, left.iSum + right.lSum);
        int rSum = max(left.rSum + right.iSum, right.rSum);
        int mSum = max(max(left.mSum, right.mSum), left.rSum + right.lSum);
        return (Status){iSum, lSum, rSum, mSum};
    }

    Status get(vector<int>& nums, int left, int right) {
        if (left == right) {
            return (Status) {nums[left], nums[left], nums[left], nums[left]};
        }
        int mid = left + (right - left) / 2;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid+1, right);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size()-1).mSum;
    }
};

    // java: 时间 7 ms, 击败 4.94%; 内存 53.6 MB, 击败 65.62%
class Solution {
    public class Status {
        public int iSum, lSum, rSum, mSum;

        public Status(int iSum, int lSum, int rSum, int mSum) {
            this.iSum = iSum;
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return get(nums, 0, nums.length-1).mSum;
    }

    public Status get(int[] nums, int left, int right) {
        if (left == right) {
            return new Status(nums[left], nums[left], nums[left], nums[left]);
        }
        int mid = left + (right - left) / 2;
        Status lSub = get(nums, left, mid);
        Status rSub = get(nums, mid+1, right);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status left, Status right) {
        int iSum = left.iSum + right.iSum;
        int lSum = Math.max(left.lSum, left.iSum + right.lSum);
        int rSum = Math.max(left.rSum + right.iSum, right.rSum);
        int mSum = Math.max(Math.max(left.mSum, right.mSum), left.rSum + right.lSum);
        return new Status(iSum, lSum, rSum, mSum);
    }
}

    // go: 时间 112 ms, 击败 17.70%; 内存 8.6 MB, 击败 93.52%
type Status struct {
    iSum, lSum, rSum, mSum int
}

func maxSubArray(nums []int) int {
    return get(nums, 0, len(nums)-1).mSum
}

func get(nums []int, left, right int) Status {
    if left == right {
        return Status{nums[left], nums[left], nums[left], nums[left]}
    }
    mid := left + (right - left) / 2
    lSub := get(nums, left, mid)
    rSub := get(nums, mid+1, right)
    return pushUp(lSub, rSub)
}

func pushUp(left, right Status) Status {
    iSum := left.iSum + right.iSum
    lSum := maxInt(left.lSum, left.iSum + right.lSum)
    rSum := maxInt(left.rSum + right.iSum, right.rSum)
    mSum := maxInt(maxInt(left.mSum, right.mSum), left.rSum + right.lSum)
    return Status{iSum, lSum, rSum, mSum}
}

func maxInt(x, y int) int {
    if x > y {
        return x
    }
    return y
}

    // javascript: 时间 96 ms, 击败 20.14%; 内存 55.2 MB, 击败 5.1%
function Status(iSum, lSum, rSum, mSum) {
    this.iSum = iSum;
    this.lSum = lSum;
    this.rSum = rSum;
    this.mSum = mSum;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    return get(nums, 0, nums.length - 1).mSum;
};

const get = (nums, left, right) => {
    if (left == right) {
        return new Status(nums[left], nums[left], nums[left], nums[left]);
    }
    let mid = left + Math.floor((right - left) / 2);
    let lSub = get(nums, left, mid);
    let rSub = get(nums, mid+1, right);
    return pushUp(lSub, rSub);
}

const pushUp = (left, right) => {
    let iSum = left.iSum + right.iSum;
    let lSum = Math.max(left.lSum, left.iSum + right.lSum);
    let rSum = Math.max(left.rSum + right.iSum, right.rSum);
    let mSum = Math.max(left.mSum, right.mSum, left.rSum + right.lSum);
    return new Status(iSum, lSum, rSum, mSum);
}
Last Updated:
Contributors: Shiqi Lu