53. Maximum subarray and
The common feature of several topics in this issue is to find a continuous array in an array to maximize the goal. We start with this problem to analyze how to solve this kind of problem.
The first is the violent solution, that is, traverse all possible continuous sub arrays and find the maximum sum. All possible continuous sub arrays have
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)
We can choose an appropriate traversal order so that each continuous subarray does not need to be summed again, so that the time complexity is
O
(
n
2
)
O(n^2)
O(n2)
//Maximum subarray sum, violent solution
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 right
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;
}
}
Now, we consider how to use dynamic programming to solve this problem.
-
First, the maximum continuous array and = max ( =\max( =Max (in) n u m s [ 0 ] nums[0] Maximum continuous array sum starting with num [0], in n u m s [ 1 ] nums[1] Maximum continuous array sum starting with num [1] , ⋯ , ,\cdots, ,, to n u m s [ n − 1 ] nums[n-1] Maximum contiguous array starting with num [n − 1] (sum)
-
set up d p [ i ] dp[i] dp[i] is n u m s [ i ] nums[i] Maximum continuous array starting with num [i] and
-
So, yes 0 ≤ i ≤ n − 2 0\leq i\leq n-2 0 ≤ i ≤ n − 2, according to d p [ i ] dp[i] The meaning of dp[i] should first include n u m s [ i ] nums[i] nums[i], and then consider whether to extend backward if d p [ i + 1 ] < 0 dp[i+1]<0 DP [i + 1] < 0, indicating that if it is included n u m s [ i + 1 ] nums[i+1] nums[i+1], no matter how backward it extends, and will only decrease further, so d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i], otherwise, it means that there are benefits for backward extension, 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], so, 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), which is the dynamic programming iterative equation of this problem
-
Obviously, we only need to store dp in an array, calculate it from back to front, and then find the maximum value in the process of traversal
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;
}
}
Complexity analysis: time complexity O ( n ) O(n) O(n), spatial complexity O ( n ) O(n) O(n)
Similarly, we find that the whole dynamic programming process only needs to use d p [ i + 1 ] dp[i+1] dp[i+1], so the spatial complexity can be further optimized to O ( 1 ) O(1) O(1)
\*Dynamic programming algorithm after optimizing spatial complexity*\
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;
}
}
If we need to find the starting and ending positions of continuous arrays exactly, we need to use dp array for backtracking.
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;
}
}
//to flash back
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};
}
}
Complexity analysis: time complexity O ( n ) O(n) Space (o), complexity O ( n ) O(n) O(n)
918. Maximum sum of circular subarrays
For circular subarray, we can see it in two cases:
- If the maximum and subarray contain n u m s [ 0 ] nums[0] nums[0] or n u m s [ n − 1 ] nums[n-1] nums[n − 1], then we can all regard it as a continuous subarray with the smallest sum removed from the whole array.
No matter which of the above three cases, the total array sum is the blue subarray sum plus the green subarray sum. To make the blue subarray sum maximum, you only need to make the green subarray sum minimum. However, there is a special case that the whole array may be excluded. In this way, the sum of the blue subarray is 0. Of course, you can not take any element, At this time, the sum of the green subarray is 0.
-
If neither n u m s [ 0 ] nums[0] nums[0], neither n u m s [ n − 1 ] nums[n-1] nums[n − 1], which is reduced to the problem of finding the maximum sum of subarrays in the range of 1 to n-2, only need to compare the maximum sum in the two cases
-
In fact, simply comparing the maximum sum of the above two cases may also cause problems. For example, if the numbers of the array are all negative, then the maximum sum is the maximum negative number, but the result obtained according to the above algorithm will be 0. In fact, if the arrays are all negative, the sum of the largest subarray in the range from 1 to n-2 must be negative, and conversely, if the sum of the largest subarray in the range from 1 to n-2 is negative, assuming that there is a positive number in the range from 1 to n-2, then take this positive number as a separate subarray, and its sum is positive, which contradicts the sum of the largest subarray, Therefore, the range from 1 to n-2 must be all negative. At this time, check the maximum sum of the first case. If it is not 0, there will be no special case above. Otherwise, check whether num [0] and num [n-1] are less than 0. If they are less than 0, it means that the boundary condition is touched, and special treatment shall be made.
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{
//When there is at least one num [0] or num [n-1], the time complexity O(n) and the space complexity 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);
//Excluding nums[0] and 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);
}
}
//Exclude boundary
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);
}
}
Complexity analysis: time complexity O ( n ) O(n) O(n), spatial complexity O ( 1 ) O(1) O(1)
Of course, if you want to obtain the maximum and sub arrays, you need to keep the dp array for backtracking. The backtracking method is similar to the above and will not be repeated. At this time, the time complexity is O ( n ) O(n) O(n), space complexity is O ( n ) O(n) O(n).
152. Product maximum subarray
The biggest difference between this problem and the maximum and subarray problem is that negative integers multiplied by negative integers may also be positive integers. We still use d p [ i ] dp[i] dp[i] is expressed as n u m s [ i ] nums[i] Num [i] is the subarray with the largest product at the beginning.
-
If n u m s [ i ] = 0 nums[i]=0 nums[i]=0, then no matter how it extends, the product is 0, d p [ i ] = 0 dp[i]=0 dp[i]=0
-
If n u m s [ i ] > 0 nums[i]>0 Num [i] > 0, if n u m s [ i + 1 ] nums[i+1] The subarray products starting with num [i + 1] are 0 or negative numbers. At this time d p [ i + 1 ] ≤ 0 dp[i+1]\leq 0 dp[i+1] ≤ 0, then extending backward will only reduce the product. At this time d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]； If n u m s [ i + 1 ] nums[i+1] nums[i+1] backward extension can be positive because it is assumed here n u m s [ i ] nums[i] nums[i] are positive integers, so it is beneficial to extend backward to n u m s [ i + 1 ] nums[i+1] nums[i+1] is the last element of the subsequence with the largest product at the beginning. By definition, 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]
-
If n u m s [ i ] < 0 nums[i]<0 Num [i] < 0, if n u m s [ i + 1 ] = 0 nums[i+1]=0 nums[i+1]=0. At this time, the backward extension product is 0, and in any case, the backward extension product is 0, but it is larger than the backward extension product. At this time, d p [ i ] = 0 dp[i]=0 dp[i]=0, if n u m s [ i + 1 ] nums[i+1] nums[i+1] is the product of the backward extension of the head, which can be negative. Then the backward extension to the product is the smallest and the absolute value is the largest. Let d p 2 [ i + 1 ] dp2[i+1] dp2[i+1] n u m s [ i + 1 ] nums[i+1] nums[i+1] extends the subarray with the smallest product backward, then 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], but if d p 2 [ i + 1 ] > 0 dp2[i+1]>0 If DP2 [i + 1] > 0, then no matter how it is extended later, the product can only become smaller, so our choice is not to extend, d p [ i ] = n u m s [ i ] dp[i]=nums[i] dp[i]=nums[i]
Therefore, we can see that we need to maintain another dp2. We will discuss dp2 in the same way:
-
If n u m s [ i ] = 0 nums[i]=0 nums[i]=0. No matter how it is extended later, the product is 0, d p 2 [ i ] = 0 dp2[i]=0 dp2[i]=0
-
If n u m s [ i ] > 0 nums[i]>0 Num [i] > 0, if d p 2 [ i + 1 ] < = 0 dp2[i+1]<=0 DP2 [i + 1] < = 0. If it extends backward, the product is negative or 0. If it does not extend backward, the product is positive, 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]； If d p 2 [ i + 1 ] > 0 dp2[i+1]>0 If DP2 [i + 1] > 0, the backward extension product will further increase, d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]
-
If n u m s [ i ] < 0 nums[i]<0 Num [i] < 0, if d p [ i + 1 ] = 0 dp[i+1]=0 No matter how the product I = 0, DP = 0, d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]； If d p [ i + 1 ] < 0 dp[i+1]<0 DP [i + 1] < 0, the backward extension product will change from negative to positive, so it is necessary to choose not to extend backward, d p 2 [ i ] = n u m s [ i ] dp2[i]=nums[i] dp2[i]=nums[i]； If d p [ i + 1 ] > 0 dp[i+1]>0 DP [i + 1] > 0, extend backward to the maximum product, multiply by n u m s [ i ] nums[i] The product of nums[i] will be the smallest, so, 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;
}
}
The whole dynamic programming process only takes d p 1 [ i + 1 ] dp1[i+1] dp1[i+1] and d p 2 [ i + 1 ] dp2[i+1] dp2[i+1], therefore, the spatial complexity can be optimized to 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. Longest subarray length with positive product
Inspired by the previous question, d p 1 [ i ] dp1[i] dp1[i] indicates in n u m s [ i ] nums[i] Num [i] is the longest subarray with positive product, d p 2 [ i ] dp2[i] dp2[i] n u m s [ i ] nums[i] nums[i] is the subarray whose longest product is negative, and the recursive equation of dynamic programming is as follows:
-
If n u m s [ i ] = 0 nums[i]=0 nums[i]=0, then the product after multiplication is 0 anyway, d p 1 [ i ] = d p 2 [ i ] = 0 dp1[i]=dp2[i]=0 dp1[i]=dp2[i]=0
-
If n u m s [ i ] > 0 nums[i]>0 Num [i] > 0, then 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
-
If n u m s [ i ] < 0 nums[i]<0 Num [i] < 0, then 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
-
It should be noted that one boundary condition is 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, if 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, if 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
The time complexity is O ( n ) O(n) O(n), the spatial complexity can be optimized to 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;
}
}
Optimize space complexity:
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;
}
}