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

本期题目
53.最大子数组和
918.环形子数组最大和
152.乘积最大子数组
1567. 乘积为正数的最长子数组长度

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;
	}
}

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

  1. 首先,最大连续数组和 = 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]开头的最大连续数组和)

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

  3. 那么,对 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),这是这个问题的动态规划迭代方程

  4. 显然,我们只需要把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. 环形子数组最大和

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

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

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

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

  1. 如果既不含 n u m s [ 0 ] nums[0] nums[0],也不含 n u m s [ n − 1 ] nums[n-1] nums[n−1],就化为了1到n-2的范围内,求最大子数组和的问题,只需要比较两种情况下的最大和即可

  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]为开头的乘积最大的子数组。

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

  2. 如果 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]

  3. 如果 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我们进行同样地讨论:

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

  2. 如果 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]

  3. 如果 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]为开头的最长乘积为负的子数组,动态规划递归方程如下:

  1. 如果 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

  2. 如果 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

  3. 如果 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

  4. 需要注意的是:有一个边界条件就是 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;
	}
}
上一篇:基于SpringMVC+MyBatis+Vue实现客户关系管理平台(CRUD)


下一篇:数论 期望 lgCF235B题解