题目
给你一个整数数组 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 <stdbool.h>
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函数
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，则从当前元素重新开始计算子数组和，否则继续累加当前元素。记录遍历过程中遇到的最大子数组和。
拆解分析
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);
}
思路分析
这套代码用了分治法方法。
通过分治法，将数组分为两部分，递归地求解左半部分、右半部分和跨中间部分的最大子数组和。最后返回这三部分中的最大值。
拆解分析
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函数的解析：
- 计算跨中间部分的最大子数组和，分别从中间向左和向右遍历计算最大和。
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函数的解析：
- 递归地求解左半部分、右半部分和跨中间部分的最大子数组和。
- 返回这三部分中的最大值。
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)。
结果
暴力破解：
动态规划：
分治法：
