53. 最大子数组和

题目

给你一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

代码

完整代码

#include 

int maxSubArray(int* nums, int numsSize) {
    int sum = 0;
    int maxSum = nums[0];
    bool haveMoreThan0 = false;
    for (int i = 0; i < numsSize; i++)
    {
        if(nums[i] < 0)
        {
            if(haveMoreThan0)
            {
                continue;
            }
        }
        else
        {
            haveMoreThan0 = true;
        }
        sum = 0;
        for (int j = i; j < numsSize; j++)
        {
            sum += nums[j];
            maxSum = maxSum < sum ? sum : maxSum;
        }
    }
    return maxSum;
}

思路分析

这套代码用了暴力法。

通过嵌套的两层循环，遍历所有可能的子数组并计算它们的和，记录其中的最大和。外层循环确定子数组的起始位置，内层循环计算从该起始位置到数组末尾的所有子数组的和。

拆解分析

1. maxSubArray函数

int maxSubArray(int* nums, int numsSize) {
    int sum = 0;
    int maxSum = nums[0];
    bool haveMoreThan0 = false;
    for (int i = 0; i < numsSize; i++)
    {
        if(nums[i] < 0)
        {
            if(haveMoreThan0)
            {
                continue;
            }
        }
        else
        {
            haveMoreThan0 = true;
        }
        sum = 0;
        for (int j = i; j < numsSize; j++)
        {
            sum += nums[j];
            maxSum = maxSum < sum ? sum : maxSum;
        }
    }
    return maxSum;
}

maxSubArray函数的解析：

• sum变量用于计算当前子数组的和。
• maxSum变量用于记录当前最大子数组和。
• haveMoreThan0变量用于判断是否有正数存在，若存在则跳过负数子数组。
• 外层循环遍历数组中的每个元素作为子数组的起始位置。
• 内层循环计算从起始位置到数组末尾的子数组和，并更新最大和。

复杂度分析

• 时间复杂度：由于使用了两层嵌套循环，时间复杂度为 O(n^2)。
• 空间复杂度：只使用了常数个额外变量，空间复杂度为 O(1)。

一题多解

动态规划

完整代码

int maxSubArray(int* nums, int numsSize) {
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < numsSize; i++) {
        currentSum = (currentSum > 0) ? (currentSum + nums[i]) : nums[i];
        maxSum = (maxSum > currentSum) ? maxSum : currentSum;
    }
    return maxSum;
}

思路分析

这套代码用了动态规划方法。

通过遍历数组，动态更新当前子数组的最大和。如果当前子数组的和小于0，则从当前元素重新开始计算子数组和，否则继续累加当前元素。记录遍历过程中遇到的最大子数组和。

拆解分析

1. maxSubArray函数

int maxSubArray(int* nums, int numsSize) {
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (int i = 1; i < numsSize; i++) {
        currentSum = (currentSum > 0) ? (currentSum + nums[i]) : nums[i];
        maxSum = (maxSum > currentSum) ? maxSum : currentSum;
    }
    return maxSum;
}

maxSubArray函数的解析：

• currentSum变量用于记录当前子数组的和。
• maxSum变量用于记录最大子数组的和。
• 遍历数组中的每个元素，如果当前子数组的和大于0，则继续累加当前元素，否则从当前元素重新开始计算子数组和。
• 更新最大子数组和。

复杂度分析

• 时间复杂度：遍历了数组一次，时间复杂度为 O(n)。
• 空间复杂度：只使用了常数个额外变量，空间复杂度为 O(1)。

分治法

完整代码

int maxCrossingSum(int* nums, int left, int mid, int right) {
    int sum = 0;
    int leftSum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }

    sum = 0;
    int rightSum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }

    return leftSum + rightSum;
}

int maxSubArraySum(int* nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int mid = (left + right) / 2;

    int leftMax = maxSubArraySum(nums, left, mid);
    int rightMax = maxSubArraySum(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);

    return (leftMax > rightMax) ? ((leftMax > crossMax) ? leftMax : crossMax) : ((rightMax > crossMax) ? rightMax : crossMax);
}

int maxSubArray(int* nums, int numsSize) {
    return maxSubArraySum(nums, 0, numsSize - 1);
}

思路分析

这套代码用了分治法方法。

通过分治法，将数组分为两部分，递归地求解左半部分、右半部分和跨中间部分的最大子数组和。最后返回这三部分中的最大值。

拆解分析

1. maxCrossingSum函数

int maxCrossingSum(int* nums, int left, int mid, int right) {
    int sum = 0;
    int leftSum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }

    sum = 0;
    int rightSum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }

    return leftSum + rightSum;
}

maxCrossingSum函数的解析：

• 计算跨中间部分的最大子数组和，分别从中间向左和向右遍历计算最大和。

2. maxSubArraySum函数

int maxSubArraySum(int* nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int mid = (left + right) / 2;

    int leftMax = maxSubArraySum(nums, left, mid);
    int rightMax = maxSubArraySum(nums, mid + 1, right);
    int crossMax = maxCrossingSum(nums, left, mid, right);

    return (leftMax > rightMax) ? ((leftMax > crossMax) ? leftMax : crossMax) : ((rightMax > crossMax) ? rightMax : crossMax);
}

maxSubArraySum函数的解析：

• 递归地求解左半部分、右半部分和跨中间部分的最大子数组和。
• 返回这三部分中的最大值。

3. maxSubArray函数

int maxSubArray(int* nums, int numsSize) {
    return maxSubArraySum(nums, 0, numsSize - 1);
}

maxSubArray

函数的解析：

• 调用maxSubArraySum函数，传入整个数组的范围（0到numsSize - 1），返回最大子数组和。

复杂度分析

• 时间复杂度：每次递归分为两部分，每部分递归遍历，时间复杂度为 O(n log n)。
• 空间复杂度：递归调用栈的深度为 log n，空间复杂度为 O(log n)。

结果

暴力破解：

动态规划：

分治法：