# AcWing 1239. Solution to the maximum product problem using two pointers greedy

## topic

## Ideas

Here we can discuss on a case-by-case basis:

serial number | Condition | How to take | final value case |
---|---|---|---|

1. | k = = n k==n k==n | Take all n n numbers | Depends on the original sequence |

2. | k < n k<n k<n and k is even | If there is an even number of negative numbers, then when we take them, we have to take them in pairs, and we cannot take an odd number of negative numbers; if there are an odd number of negative numbers, then we only need to take the negative numbers in pairs. | The result must be non-negative |

3. | k < n k<n k<n and k is odd | If all numbers are negative, then taking the product of an odd number of negative numbers will always be a negative number; if there is at least one non-negative number, then we can take this non-negative number first, and then add n − 1 n-1 n−1 numbers Select k − 1 k-1 k−1 numbers. The problem returns to the second case, and the result must be non-negative. | In the first case the result is negative, in the second case the result must be non-negative |

The method can finally be summarized as a greedy + double pointer algorithm:

- Sort the sequence from small to large, so there are three possible arrangements: 1) In the sequence
**There are positive numbers and negative numbers**: Numbers with large absolute values are at both ends, the left end is a negative number with a large absolute value, the right end is a positive number with a large absolute value, and the number with a small absolute value is in the middle 2) sequence**All positive numbers**: The one with the largest absolute value is on the right end, the one with the smallest absolute value is on the left end 3) In the sequence**All negative numbers**: The larger absolute value is on the left end, and the smaller absolute value is on the right end. - If k k k is an odd number, then take the rightmost number first. It may be the largest positive number, or it may be the negative number with the smallest absolute value (corresponding to the case where all numbers are negative) (
*But no matter what the situation is, this selection can ensure that the final result is the largest. If there is at least one positive number in the sequence, the final result is a positive number, and you want the absolute value of the result to be the largest, then it will select the largest number from the beginning. taken; if the sequence is all negative numbers and the final result is a negative number, and you want the absolute value of the result to be the smallest, then it starts with the negative number with the smallest absolute value, which also ensures that the absolute value of the final negative number is the smallest, that is, the negative number maximum value*), then the problem is transformed into choosing k − 1 k-1 k−1 numbers among n − 1 n-1 n−1 numbers, because k − 1 k-1 k−1 is an even number, then the problem is transformed into the situation 1 1 1 - If k k k is an even number, then it belongs to case 1 1 1. You only need to take the larger number pair at both ends of the sorted sequence.

The implementation idea of the algorithm is**greedy**, the implementation method is**double pointer**

Details:

It says in the title

In C++, the result of taking modulo a negative number is a negative number, such as − 8 % 5 = − 3 -8\%5=-3 −8%5=−3. The question also explains the inherent properties of C++. Therefore no special treatment is required.

## code

```
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,mod=1000000009;
typedef long long LL;
int a[N];
int n,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n); //Sort
int res=1,sign=1; //res answer, sign marks whether the final result is a negative number or a positive number. If it is a negative number, the number with a smaller absolute value should be taken in the strategy of taking numbers in pairs. If it is a positive number, it should be taken in pairs. In the number strategy, the number with the largest absolute value should be chosen
int l=0,r=n-1;
if(k%2) //If k is an odd number
{
res=a[r--]; //Take the rightmost number first
k--;
if(res<0) sign=-1; // Update the symbol marker for the final answer
}
while(k)
{
LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1]; //The multiplication of two numbers may be very large, remember to define it as LL
if(x*sign>y*sign) //Control whether to judge whether the absolute value is large or small
{
res=x%mod*res%mod; //Here, x should be modulo first, then multiplied by res, and then modulo the final answer. Don't add brackets blindly, as it is easy to make mistakes. If the operation step here is x%mod multiplied by res%mod, that would be wrong. It may cause the intermediate result to explode, and in the end, you forget to take the modulo of the answer.
l+=2;
}
else
{
res=y%mod*res%mod;
r-=2;
}
k-=2; //Because it is taken in pairs, remember to subtract 2 from k
}
printf("%d",res);
return 0;
}
```