欢迎访问LeetCode题解合集
题目描述
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
题解:
法一:
三重循环,第一重循环枚举起点,第二重循环枚举终点,第三重循环求起点和终点之间的和。
时间复杂度:$O(n^3)$
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_sum = INT_MIN, sum;
for ( int i = 0; i < n; ++i ) {
for ( int j = i; j < n; ++j ) {
sum = 0;
for ( int k = i; k <= j; ++k )
sum += nums[k];
if ( sum > max_sum ) max_sum = sum;
}
}
return max_sum;
}
};
这个版本代码超时。可以优化掉第三维,求区间和可以利用前缀和搞定。
时间复杂度:$O(n^2)$
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1);
for ( int i = 1; i <= n; ++i )
f[i] = f[i - 1] + nums[i - 1];
int max_sum = INT_MIN, sum;
for ( int i = 1; i <= n; ++i ) {
for ( int j = i; j <= n; ++j ) {
sum = f[j] - f[i - 1];
if ( sum > max_sum ) max_sum = sum;
}
}
return max_sum;
}
};
/*
时间:1340ms,击败:5.08%
内存:12.9MB,击败:90.30%
*/
勉强能过这题。但是时间复杂度还是有点爆炸。。。
当然,也可以在第二重循环直接累加求和,不用开辟额外的空间。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_sum = INT_MIN, sum;
for ( int i = 0; i < n; ++i ) {
sum = 0;
for ( int j = i; j < n; ++j ) {
sum += nums[j];
if ( sum > max_sum ) max_sum = sum;
}
}
return max_sum;
}
};
/*
时间:736ms,击败:5.08%
内存:12.9MB,击败:90.45%
*/
法二:
动态规划。f[i]
表示以 nums[i]
结尾的连续子数组的最大和。那么转移方程就是:$f[i] = max(nums[i], f[i - 1] + nums[i])$
时间复杂度:$O(n)$
额外空间复杂度:$O(n)$
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
f[0] = nums[0];
int max_sum = nums[0];
for ( int i = 1; i < n; ++i ) {
f[i] = max( nums[i], f[i - 1] + nums[i] );
if ( f[i] > max_sum ) max_sum = f[i];
}
return max_sum;
}
};
/*
时间:8ms,击败:95.00%
内存:13MB,击败:88.66%
*/
法三:
分治。将一个区间 [l, r]
划分成 [l, m]
和 [m + 1, r]
两部分,那么最大子段和可能存在三种情况:
- 左边区间
- 右边区间
- 横跨左右两个区间
时间复杂度:$O(nlogn)$
class Solution {
public:
int merge( int l, int r, vector<int>& nums ) {
if ( l == r ) return nums[l];
int m = (l + r) >> 1;
int maxLeftSum = merge(l, m, nums);
int maxRighSum = merge(m + 1, r, nums);
int maxLeftBorderSum = INT_MIN;
int ans = 0;
for ( int i = m; i >= l; --i ) {
ans += nums[i];
if( ans > maxLeftBorderSum )
maxLeftBorderSum = ans;
}
int maxRighBorderSum = INT_MIN;
ans = 0;
for ( int i = m + 1; i <= r; ++i ) {
ans += nums[i];
if ( ans > maxRighBorderSum )
maxRighBorderSum = ans;
}
return max( {maxLeftSum, maxRighSum, maxLeftBorderSum + maxRighBorderSum} );
}
int maxSubArray(vector<int>& nums) {
int n = nums.size();
return merge(0, n - 1, nums);
}
};
/*
时间:12ms,击败:81.33%
内存:12.7MB,击败:99.38%
*/
法四:
贪心。
在 方法二 中,动态规划转移方程为:$f[i] = max(nums[i], f[i - 1] + nums[i])$ ,可以发现,如果 f[i - 1] < 0
,也就是以 nums[i - 1]
结尾的最大子段和是 小于0 的,那么 nums[i]
肯定不能接在 nums[i - 1]
后面(不然就是接盘侠),也就是说,需要从 i
位置从头开始求最大子段和了,前面的可以直接扔掉,所以可以贪心求解。
时间复杂度:$O(n)$
额外空间复杂度:$O(1)$
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int max_sum = INT_MIN, sum = 0;
for ( auto& it : nums ) {
if ( sum >= 0 ) sum += it;
else sum = it;
max_sum = max( max_sum, sum );
}
return max_sum;
}
};
/*
时间:4ms,击败:99.46%
内存:12.8MB,击败:96.01%
*/