动态规划3：连续子数组类问题

2023-11-05 12:14:46

本期题目

53. 最大子数组和

本期的几道题目的共同特点都是要在一个数组中找一个连续的数组，以使得目标最大化，我们从这道题入手来分析这类题目该如何求解。

首先是暴力解法，即遍历所有的可能的连续子数组，找最大的和，所有可能的连续子数组有 n + ( n − 1 ) + ( n − 2 ) + ⋯ + 1 = n ( n + 1 ) 2 n+(n-1)+(n-2)+\cdots+1=\frac{n(n+1)}{2} n+(n−1)+(n−2)+⋯+1=2n(n+1)
我们可以选择一种恰当的遍历顺序，使得每个连续子数组都不用重新求和，从而使得时间复杂度为 O ( n 2 ) O(n^2) O(n2)

//最大子数组和，暴力解法
int maxSubArray(const vector<int>& nums){
	int n=nums.size();
	if(n==1) return nums[0];
	else{
		int begin=0;
		int end=0;
		bool direction=true;//true向右
		int maxsum=nums[0];
		int sum=nums[0];
		while(end-begin<=n-2){
			if(direction){
				if(end==n-1){
					direction=false;
					sum+=nums[--begin];
				}else{
					sum-=nums[begin++];
					sum+=nums[++end];
				}
			}else{
				if(begin==0){
					direction=true;
					sum+=nums[++end];
				}else{
					sum-=nums[end--];
					sum+=nums[--begin];
				}
			}
			maxsum=max(maxsum,sum);
		}
		return maxsum;
	}
}

现在，我们考虑如何用动态规划来解决这个问题。

首先，最大连续数组和 = max ⁡ ( =\max( =max(以 n u m s [ 0 ] nums[0] nums[0]开头的最大连续数组和，以 n u m s [ 1 ] nums[1] nums[1]开头最大连续数组和 , ⋯ , ,\cdots, ,⋯,以 n u m s [ n − 1 ] nums[n-1] nums[n−1]开头的最大连续数组和)

设 d p [ i ] dp[i] dp[i]是以 n u m s [ i ] nums[i] nums[i]开头的最大连续数组和

那么，对 0 ≤ i ≤ n − 2 0\leq i\leq n-2 0≤i≤n−2，按照 d p [ i ] dp[i] dp[i]的含义，首先应当包含 n u m s [ i ] nums[i] nums[i]，然后考虑是否向后延伸，如果 d p [ i + 1 ] < 0 dp[i+1]<0 dp[i+1]<0，说明如果包含 n u m s [ i + 1 ] nums[i+1] nums[i+1]，不管后面如何向后延伸，和只会进一步减小，所以 d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]，否则，说明向后延伸还有收益， d p [ i ] = n u m s [ i ] + d p [ i + 1 ] dp[i]=nums[i]+dp[i+1] dp[i]=nums[i]+dp[i+1]，所以， d p [ i ] = n u m s [ i ] + m a x ( d p [ i + 1 ] , 0 ) dp[i]=nums[i]+max(dp[i+1],0) dp[i]=nums[i]+max(dp[i+1],0)，这是这个问题的动态规划迭代方程

显然，我们只需要把dp储存在一个数组当中，从后向前计算，然后在遍历的过程中求出最大值即可

int maxSubArray(const vector<int>& nums){
	int n=nums.size();
	if(n==0) return 0;
	else if(n==1) return nums[0];
	else{
		vector<int> dp(n,0);
		dp[n-1]=nums[n-1];
		int maxdp = dp[n-1];
		for(int i=n-2;i>=0;i--){
			dp[i]=nums[i]+max(0,dp[i+1]);
			maxdp=max(maxdp,dp[i]);
		}
		return maxdp;
	}
}

复杂度分析：时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)

同样地，我们发现整个动态规划的过程只需要用到 d p [ i + 1 ] dp[i+1] dp[i+1]，所以，空间复杂度可以进一步优化到 O ( 1 ) O(1) O(1)

\*优化空间复杂度后的动态规划算法*\
int maxSubArray(const vector<int>& nums){
	int n=nums.size();
	if(n==0) return 0;
	else if(n==1) return nums[0];
	else{
		int dp1=nums[n-1];
		int maxdp = dp1;
		for(int i=n-2;i>=0;i--){
			dp1=nums[i]+max(0,dp1);
			maxdp=max(maxdp,dp1);
		}
		return maxdp;
	}
}

如果我们需要确切地找到连续数组的起始位置和终止位置，那么，我们需要利用dp数组进行回溯。

vector<int> maxSubArray(const vector<int>& nums){
	int n=nums.size();
	if(n==0) return 0;
	else if(n==1) return nums[0];
	else{
		vector<int> dp(n,0);
		dp[n-1]=nums[n-1];
		int maxdp = dp[n-1];
		int maxi = n-1;
		for(int i=n-2;i>=0;i--){
			dp[i]=nums[i]+max(0,dp[i+1]);
			if(dp[i]>maxdp){
				maxdp=dp[i];
				maxi=i;
			}
		}
		//回溯
		int begin=maxi;
		int end=maxi;
		while(true){
			if(end<=n-2){
				if(dp[end+1]<0) break;
				else end++;
			}else break;
		}
		return {begin,end};
	}
}

复杂度分析：时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( n ) O(n) O(n)

918. 环形子数组最大和

对环形子数组，我们可以分两种情况看：

如果最大和子数组包含 n u m s [ 0 ] nums[0] nums[0]或 n u m s [ n − 1 ] nums[n-1] nums[n−1]，那么，我们都可以视为是从整个数组中刨去一个最小和的连续子数组。

不论是上面三种情况中哪种，总的数组和都是蓝色子数组和加上绿色子数组和，要使得蓝色子数组和最大，只需要使得绿色子数组和最小即可，但有一种特殊情况是可能会排除掉整个数组，这样得到的蓝色子数组和为0，当然，还可以一个元素都不取，此时绿色子数组的和为0。

如果既不含 n u m s [ 0 ] nums[0] nums[0]，也不含 n u m s [ n − 1 ] nums[n-1] nums[n−1]，就化为了1到n-2的范围内，求最大子数组和的问题，只需要比较两种情况下的最大和即可
实际上，单纯比较以上两种情况的最大和也可能会出问题，比如如果数组的数字全为负数，那么最大和为最大的负数，但是，按上面的算法得到的结果会是0。实际上，如果数组全是负数，那么1到n-2范围内最大子数组和一定是负数，并且反过来推断，如果1到n-2范围内的最大子数组和为负数，假设1到n-2范围内存在一个正数，那么取这个正数作为单独的子数组，其和为正，与最大子数组和为负数矛盾，所以1到n-2范围内一定全是负数，此时，检查第一种情况的最大和，如果不为0，那么不会存在以上的特殊情况，否则，要检查nums[0]和nums[n-1]是否小于0，如果都小于，那么就是触碰到边界条件，则要作特殊处理。

int  maxSubarraySumCircular(const  vector<int>&  nums){
	int n=nums.size();
	if(n==0) return 0;
	else if(n==1) return nums[0];
	else if(n==2) return max(nums[0],max(nums[1],nums[0]+nums[1]));
	else{
		//至少包含一个nums[0]或nums[n-1]的情况，时间复杂度O(n)，空间复杂度O(1)
		int sum=0;
		for(auto e:nums) sum+=e;
		int minsum=nums[n-1];
		int dp1=nums[n-1];
		for(int i=n-2;i>=0;i--){
			dp1=nums[i]+min(0,dp1);
			minsum=min(minsum,dp1);
		}
		minsum=min(0,minsum);
		//不包含nums[0]以及nums[n-1]
		int sum2;
		if(n==3) sum2=nums[1];
		else{
			sum2=nums[n-2];
			dp1=nums[n-2];
			for(int i=n-3;i>=1;i--){
				dp1=nums[i]+max(0,dp1);
				sum2=max(sum2,dp1);
			}
		}
		//排除边界
		if(sum2<0&&nums[0]<0&&nums[n-1]<0) return max(sum2,max(nums[0],nums[n-1]));
		else return max(sum2,sum-minsum);
	}
}

复杂度分析：时间复杂度 O ( n ) O(n) O(n)，空间复杂度 O ( 1 ) O(1) O(1)

当然，如果想要获得最大和子数组，则需要保留dp数组进行回溯，回溯方法和上面类似，不再赘述。此时时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)。

152. 乘积最大子数组

这个问题和最大和子数组问题的最大区别是，负整数乘以负整数也可能是正整数，我们还是以 d p [ i ] dp[i] dp[i]表示为 n u m s [ i ] nums[i] nums[i]为开头的乘积最大的子数组。

如果 n u m s [ i ] = 0 nums[i]=0 nums[i]=0，那么后面无论怎么延伸，乘积都是0， d p [ i ] = 0 dp[i]=0 dp[i]=0

如果 n u m s [ i ] > 0 nums[i]>0 nums[i]>0，如果以 n u m s [ i + 1 ] nums[i+1] nums[i+1]开头的子数组乘积都是0或负数，此时 d p [ i + 1 ] ≤ 0 dp[i+1]\leq 0 dp[i+1]≤0，那么向后延伸只会减小乘积，此时 d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]；如果 n u m s [ i + 1 ] nums[i+1] nums[i+1]向后延伸可以为正数，因为这里假定 n u m s [ i ] nums[i] nums[i]都是正整数，因此向后延伸是有好处的，延伸到以 n u m s [ i + 1 ] nums[i+1] nums[i+1]为开头乘积最大的子序列的最后一个元素为止，按照定义， d p [ i ] = n u m s [ i ] × d p [ i + 1 ] dp[i]=nums[i]\times dp[i+1] dp[i]=nums[i]×dp[i+1]

如果 n u m s [ i ] < 0 nums[i]<0 nums[i]<0，如果 n u m s [ i + 1 ] = 0 nums[i+1]=0 nums[i+1]=0，此时向后延伸乘积为0，并且无论如何向后延伸乘积都是0，但比向后延伸的乘积要大，此时， d p [ i ] = 0 dp[i]=0 dp[i]=0，如果 n u m s [ i + 1 ] nums[i+1] nums[i+1]为头向后延伸的乘积可以是负数，那么向后延伸到乘积最小，绝对值最大，设 d p 2 [ i + 1 ] dp2[i+1] dp2[i+1]为以 n u m s [ i + 1 ] nums[i+1] nums[i+1]向后延伸乘积最小的子数组，则 d p [ i ] = n u m s [ i ] × d p 2 [ i + 1 ] dp[i]=nums[i]\times dp2[i+1] dp[i]=nums[i]×dp2[i+1]，但如果 d p 2 [ i + 1 ] > 0 dp2[i+1]>0 dp2[i+1]>0，那么无论后面如何延伸，乘积只能变小，那我们的选择是不延伸， d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]

于是我们可以看到，我们还需要另外维护一个dp2，对dp2我们进行同样地讨论：

如果 n u m s [ i ] = 0 nums[i]=0 nums[i]=0，无论后面怎么延伸，乘积都为0， d p 2 [ i ] = 0 dp2[i]=0 dp2[i]=0

如果 n u m s [ i ] > 0 nums[i]>0 nums[i]>0，如果 d p 2 [ i + 1 ] < = 0 dp2[i+1]<=0 dp2[i+1]<=0，如果向后延伸，乘积就为负数或0，不向后延伸，乘积为正数， d p 2 [ i ] = n u m s [ i ] × d p [ i + 1 ] dp2[i]=nums[i]\times dp[i+1] dp2[i]=nums[i]×dp[i+1]；如果 d p 2 [ i + 1 ] > 0 dp2[i+1]>0 dp2[i+1]>0，向后延伸乘积会进一步增大， d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]

如果 n u m s [ i ] < 0 nums[i]<0 nums[i]<0，如果 d p [ i + 1 ] = 0 dp[i+1]=0 dp[i+1]=0，说明无论后面如何延伸，乘积都是0， d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]；如果 d p [ i + 1 ] < 0 dp[i+1]<0 dp[i+1]<0，向后延伸乘积会从负数变正数，因此有必要选择不向后延伸， d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]；如果 d p [ i + 1 ] > 0 dp[i+1]>0 dp[i+1]>0，向后延伸到乘积最大，乘上 n u m s [ i ] nums[i] nums[i]乘积就会最小，因此， d p 2 [ i ] = n u m s [ i ] × d p [ i + 1 ] dp2[i]=nums[i]\times dp[i+1] dp2[i]=nums[i]×dp[i+1]

int maxProduct(const vector<int>& nums){
	int n=nums.size();
	if(n==1) return nums[0];
	else{
		vector<int> dp1(n,0);
		vector<int> dp2(n,0);
		dp1[n-1]=nums[n-1];
		dp2[n-1]=nums[n-1];
		int maxprod = nums[n-1];
		for(int i=n-2;i>=0;i--){
			if(nums[i]==0){
				dp1[i]=0;
				dp2[i]=0;
			}else if(nums[i]>0){
				if(dp1[i+1]<=0) dp1[i]=nums[i];
				else dp1[i]=nums[i]*dp1[i+1];
				if(dp2[i+1]>0) dp2[i]=nums[i];
				else dp2[i]=nums[i]*dp2[i+1];
			}else{
				if(dp2[i+1]<=0) dp1[i]=nums[i]*dp2[i+1];
				else dp1[i]=nums[i];
				if(dp1[i+1]<=0) dp2[i]=nums[i];
				else dp2[i]=nums[i]*dp1[i+1];
			}
			maxprod=max(maxprod,dp1[i]);
		}
		return maxprod;
	}
}

整个动态规划的过程只用到了 d p 1 [ i + 1 ] dp1[i+1] dp1[i+1]和 d p 2 [ i + 1 ] dp2[i+1] dp2[i+1]，因此，可以将空间复杂度优化到 O ( 1 ) O(1) O(1)

int maxProduct(const vector<int>& nums){
	int n=nums.size();
	if(n==1) return nums[0];
	else{
		int dp1=nums[n-1];
		int dp2=nums[n-1];
		int maxprod = nums[n-1];
		for(int i=n-2;i>=0;i--){
			if(nums[i]==0){
				dp1=0;
				dp2=0;
			}else if(nums[i]>0){
				int tmp1=dp1;
				int tmp2=dp2;
				if(tmp1<=0) dp1=nums[i];
				else dp1=nums[i]*tmp1;
				if(tmp2>0) dp2=nums[i];
				else dp2=nums[i]*tmp2;
			}else{
				int tmp1=dp1;
				int tmp2=dp2;
				if(tmp2<=0) dp1=nums[i]*tmp2;
				else dp1=nums[i];
				if(tmp1<=0) dp2=nums[i];
				else dp2=nums[i]*tmp1;
			}
			maxprod=max(maxprod,dp1);
		}
		return maxprod;
	}
}

1567. 乘积为正数的最长子数组长度

受到上一题的启发， d p 1 [ i ] dp1[i] dp1[i]表示以 n u m s [ i ] nums[i] nums[i]为开头的最长乘积为正的子数组， d p 2 [ i ] dp2[i] dp2[i]为以 n u m s [ i ] nums[i] nums[i]为开头的最长乘积为负的子数组，动态规划递归方程如下：

如果 n u m s [ i ] = 0 nums[i]=0 nums[i]=0，那么无论如何相乘后面乘积都是0， d p 1 [ i ] = d p 2 [ i ] = 0 dp1[i]=dp2[i]=0 dp1[i]=dp2[i]=0

如果 n u m s [ i ] > 0 nums[i]>0 nums[i]>0，那么 d p 1 [ i ] = d p 1 [ i + 1 ] + 1 ， d p 2 [ i ] = d p 2 [ i + 1 ] + 1 dp1[i]=dp1[i+1]+1，dp2[i]=dp2[i+1]+1 dp1[i]=dp1[i+1]+1，dp2[i]=dp2[i+1]+1

如果 n u m s [ i ] < 0 nums[i]<0 nums[i]<0，那么 d p 1 [ i ] = 1 + d p 2 [ i + 1 ] ， d p 2 [ i + 1 ] = d p 1 [ i + 1 ] + 1 dp1[i]=1+dp2[i+1]，dp2[i+1]=dp1[i+1]+1 dp1[i]=1+dp2[i+1]，dp2[i+1]=dp1[i+1]+1

需要注意的是：有一个边界条件就是 d p 1 [ i + 1 ] = d p 2 [ i + 1 ] = 0 dp1[i+1]=dp2[i+1]=0 dp1[i+1]=dp2[i+1]=0，此时如果 n u m s [ i ] > 0 ， d p 1 [ i ] = 1 ， d p 2 [ i ] = 0 nums[i]>0，dp1[i]=1，dp2[i]=0 nums[i]>0，dp1[i]=1，dp2[i]=0，如果 n u m s [ i ] < 0 ， d p 1 [ i ] = 0 ， d p 2 [ i ] = 1 nums[i]<0，dp1[i]=0，dp2[i]=1 nums[i]<0，dp1[i]=0，dp2[i]=1

时间复杂度为 O ( n ) O(n) O(n)，空间复杂度可以优化至 O ( 1 ) O(1) O(1)

int  getMaxLen(vector<int>&  nums) {
	int n = nums.size();
	if(n==1) return (nums[0]>0)?1:0;
	else{
		vector<int> dp_positive(n,0);
		vector<int> dp_negative(n,0);
		dp_positive[n-1] = (nums[n-1]>0)?1:0;
		dp_negative[n-1] = (nums[n-1]<0)?1:0;
		int maxLen = (nums[n-1]>0)?1:0;
		for(int i=n-2;i>=0;i--){
			if(nums[i]>0){
				dp_positive[i] = dp_positive[i+1]+1;
				dp_negative[i] = (dp_negative[i+1]>0)?(dp_negative[i+1]+1):0;
			}else if(nums[i]==0){
				dp_positive[i] = 0;
				dp_negative[i] = 0;
			}else{
				dp_positive[i] = (dp_negative[i+1]>0)?(dp_negative[i+1]+1):0;
				dp_negative[i] = dp_positive[i+1]+1;
			}
			maxLen = (maxLen>dp_positive[i])?maxLen:dp_positive[i];
		}
		return maxLen;
	}
}

优化空间复杂度：

int  getMaxLen(vector<int>&  nums) {
	int n = nums.size();
	if(n==1) return (nums[0]>0)?1:0;
	else{
		int dp_positive = (nums[n-1]>0)?1:0;
		int dp_negative = (nums[n-1]<0)?1:0;
		int maxLen = (nums[n-1]>0)?1:0;
		for(int i=n-2;i>=0;i--){
			int tmp1 =dp_positive;
			int tmp2 =dp_negative;
			if(nums[i]>0){
				dp_positive = tmp1+1;
				dp_negative = (tmp2>0)?(tmp2+1):0;
			}else if(nums[i]==0){
				dp_positive = 0;
				dp_negative = 0;
			}else{
				dp_positive = (tmp2>0)?(tmp2+1):0;
				dp_negative = tmp1+1;
			}
			maxLen = (maxLen>dp_positive)?maxLen:dp_positive;
		}
		return maxLen;
	}
}

码农公寓

53. 最大子数组和

918. 环形子数组最大和

152. 乘积最大子数组

1567. 乘积为正数的最长子数组长度

相关文章