英文原文
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
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 <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
通过代码
高赞题解
<
,
,
,
>
代码：
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int max = INT_MIN;
int numsSize = int(nums.size());
for (int i = 0; i < numsSize; i++)
{
int sum = 0;
for (int j = i; j < numsSize; j++)
{
sum += nums[j];
if (sum > max)
{
max = sum;
}
}
}
return max;
}
};
<
,
,
,
,
,
,
,
,
,
,
>
代码：
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
//dp[i]表示nums中以nums[i]结尾的最大子序和
vector<int> dp(numsSize);
dp[0] = nums[0];
result = dp[0];
for (int i = 1; i < numsSize; i++)
{
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
result = max(result, dp[i]);
}
return result;
}
};
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
//因为只需要知道dp的前一项，我们用int代替一维数组
int dp(nums[0]);
result = dp;
for (int i = 1; i < numsSize; i++)
{
dp = max(dp + nums[i], nums[i]);
result = max(result, dp);
}
return result;
}
};
<
,
,
,
,
,
,
,
,
>
代码：
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
int sum = 0;
for (int i = 0; i < numsSize; i++)
{
sum += nums[i];
result = max(result, sum);
//如果sum < 0，重新开始找子序串
if (sum < 0)
{
sum = 0;
}
}
return result;
}
};
<
,
,
,
,
,
,
,
,
,
,
>
代码：
class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
result = maxSubArrayHelper(nums, 0, numsSize - 1);
return result;
}
int maxSubArrayHelper(vector<int> &nums, int left, int right)
{
if (left == right)
{
return nums[left];
}
int mid = (left + right) / 2;
int leftSum = maxSubArrayHelper(nums, left, mid);
//注意这里应是mid + 1，否则left + 1 = right时，会无线循环
int rightSum = maxSubArrayHelper(nums, mid + 1, right);
int midSum = findMaxCrossingSubarray(nums, left, mid, right);
int result = max(leftSum, rightSum);
result = max(result, midSum);
return result;
}
int findMaxCrossingSubarray(vector<int> &nums, int left, int mid, int right)
{
int leftSum = INT_MIN;
int sum = 0;
for (int i = mid; i >= left; i--)
{
sum += nums[i];
leftSum = max(leftSum, sum);
}
int rightSum = INT_MIN;
sum = 0;
//注意这里i = mid + 1，避免重复用到nums[i]
for (int i = mid + 1; i <= right; i++)
{
sum += nums[i];
rightSum = max(rightSum, sum);
}
return (leftSum + rightSum);
}
};
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 765556 | 1383530 | 55.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 买卖股票的最佳时机 | 简单 |
| 乘积最大子数组 | 中等 |
| 数组的度 | 简单 |
| 最长湍流子数组 | 中等 |
