乘积最大

题目 乘积最大

思路分析

如果 k == n ,那么就证明所有的数字是全部都选,

如果 k < n , 那么就要思考怎样去选择了:

  k 如果是偶数的话,选出来的结果一定是非负数 , 原因如下:

        负数的个数是偶数个的话,负负得正,那么一定是非负数

        负数的个数如果是奇数个的话,那么我们就只选偶数个绝对值最大的负数

  k 如果是奇数个的话,

        所有的数字如果都是负数,那么选出来的结果也一定都是负数

        否则的话,则一定至少有 1个非负数, 那么我们将最大的数取出来,

此时要选的个数就是 k--,

        k-- 是偶数,那么就又转化为 k-- 是偶数的情况思考

 这里可以巧妙一下 k是奇数的情况 先把最大的数取出来 如果是小于0就说明全小于0 最后答案一定为
 负 如果大于0 就变成前面一样情况处理

从左右分别往里逼近去选 类似于归并排序 把左边当成一个集合 右边当成一个集合 左边的俩是左边乘积最大的 右边的俩是右边乘积最大的 他们之间做双指针 就可以取出乘积全局最大的俩

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=100010,mod=1000000009;

int a[N];

int n,k;

int main()

{

    cin>>n>>k;

    for(int i=0;i<n;i++)

        cin>>a[i];

    sort(a,a+n);

    LL res=1;

    int l=0,r=n-1;

    int sign=1;//符号 一开始令为正

    if(k&1){

        res=a[r];//奇数时 把最大的先取出来 问题转变成偶数情况

        r--;

        k--;

        if(res<0)

            sign=-1;//若最大的都是负 说明全是负数 最后答案一定是负的（奇数个且全负）

    }

    while(k){

        LL x=(LL)a[l]*a[l+1],y=(LL)a[r]*a[r-1];

        if(x*sign>y*sign){

            res=x%mod*res%mod;

            //不可以写成(x*res)%mod ,也不可以写成res%mod*x%mod

            //x最大是10^10，如果不先取模的话，和res相乘的结果最大是10^19,会爆long long

            l+=2;

        }

        else{

            res=y%mod*res%mod;

            r-=2;

        }

        k-=2;

    }

    cout<<res;

    return 0;

}

同类题型

视频讲解

⬅️ 三国游戏 🏠 00-刷题理模型 ➡️ 排序 权贪心（短作业优先 重权值优先）