每日一题之乘积最大

题目描述

给定 N 个整数 A1,A2,⋯AN。请你从中选出 K 个数,使其乘积最大。

请你求出最大的乘积,由于乘积可能超出整型范围,你只需输出乘积除以 109+9 的余数。

注意,如果 X<0,我们定义 X 除以 109+9 的余数是负(−X)除以 109+9的余数。

即:0−((0−x)%109+9)。

输入描述

输入格式:

第一行包含两个整数 N,K。

以下 N 行每行一个整数 Ai​。

其中,1≤K≤N≤105,−105≤Ai≤105。

输出描述

输出一个整数,表示答案。

思路分析:

情况 1:k == n

  • 如果 k == n,说明我们需要选择数组中所有的数。

  • 此时,无论数组中的数是正数还是负数,最终的结果就是所有数的乘积。

  • 不需要额外的选择策略。


情况 2:k < n

当 k < n 时,我们需要选择部分数。此时,我们需要根据 k 的奇偶性以及数组中负数的个数来决定选择策略。

子情况 1:k 是偶数
  • 目标:选出的结果一定是非负数。

  • 原因

    1. 如果负数的个数是偶数个,那么我们可以成对选择负数(负负得正),最终结果是非负数。

    2. 如果负数的个数是奇数个,我们可以只选择偶数个绝对值最大的负数,剩下的选择正数,最终结果仍然是非负数。

  • 策略

    • 使用双指针法,每次比较数组左端两个数的乘积和右端两个数的乘积,选择乘积较大的一对。

    • 重复这个过程,直到选出 k 个数。

子情况 2:k 是奇数
  • 目标:选出的结果可能是负数或非负数,取决于数组中的元素。

  • 子情况分析

    1. 如果数组中所有数都是负数

      • 选出的结果一定是负数。

      • 因为奇数个负数的乘积仍然是负数。

    2. 如果数组中至少有一个非负数

      • 我们可以先选择最大的一个数(一定是非负数),此时剩下的 k-1 个数是偶数个。

      • 问题转化为 k-1 是偶数的情况,按照偶数策略选择即可。

  • 策略

    • 先选择数组中最大的一个数(如果存在非负数,则选择最大的非负数;否则选择最大的负数)。

    • 然后对剩下的 k-1 个数,按照偶数策略选择。

#include <iostream>
#include <algorithm>
using namespace std;const int N = 100010, M = 1000000009;  // 定义常量N和M,N为数组最大长度,M为模数
typedef long long ll;  // 定义long long类型为ll,方便使用ll a[N];  // 定义数组a,用于存储输入的整数
int n, k;  // n为数组长度,k为需要选择的元素个数
ll res = 1;  // 初始化结果为1,用于存储最终的乘积结果int main()
{cin >> n >> k;  // 输入数组长度n和需要选择的元素个数kfor(int i = 0; i < n; i++){cin >> a[i];  // 输入数组元素}sort(a, a + n);  // 对数组进行排序,方便后续处理int l = 0, r = n - 1;  // 定义双指针,l指向数组最左端,r指向数组最右端int sigh = 1;  // 符号标记,初始为1,表示结果为正数// 当k为奇数时,至少取一个最大的数while(k % 2){res = a[r];  // 取当前最大的数r--;  // 右指针左移k--;  // k减1,表示已经取了一个数if(res < 0) sigh = -1;  // 如果取的数为负数,则标记符号为-1}// 双指针法处理剩余的k个数while(k){ll x = a[l] * a[l + 1];  // 计算左端两个数的乘积ll y = a[r] * a[r - 1];  // 计算右端两个数的乘积// 根据符号标记和乘积大小决定取哪一对数if(x * sigh > y * sigh){res = x % M * res % M;  // 取左端的两个数,并更新结果l += 2;  // 左指针右移两位}else{res = y % M * res % M;  // 取右端的两个数,并更新结果r -= 2;  // 右指针左移两位}k -= 2;  // k减2,表示已经取了两个数}cout << res << endl;  // 输出最终结果return 0;  // 程序结束
}

代码实现思路

  1. 排序数组

    • 将数组排序,方便使用双指针法选择数。

  2. 处理 k 是奇数的情况

    • 先选择最大的一个数,并更新结果和符号标记。

    • 将 k 减 1,转化为偶数情况。

  3. 处理 k 是偶数的情况

    • 使用双指针法,每次选择左端或右端乘积较大的一对数。

    • 更新结果,直到选出 k 个数。

  4. 输出结果

    • 最终输出计算得到的乘积结果

总结:就是先判断k是奇数还是偶数,若是偶数,先取出最大的数,将k变为偶数。当k为偶数,我们只需要分别从左右两边去找最大的一对乘积,也就是看看到底是两个负数相乘的结果大还是两个正数相乘的结果大。

这道题的标签是动态规划,现在附上动态规划的代码,不过会超时。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;const int MOD = 1e9 + 9;  // 定义模数
const long long INF = 1e18;  // 定义无穷大int main() {int N, K;cin >> N >> K;vector<int> A(N);for (int i = 0; i < N; i++) {cin >> A[i];}// 初始化 DP 表vector<vector<long long>> dp(N + 1, vector<long long>(K + 1, -INF));dp[0][0] = 1;  // 从 0 个数中选出 0 个数,乘积为 1// 动态规划求解for (int i = 1; i <= N; i++) {for (int j = 0; j <= K; j++) {// 不选 A[i-1]dp[i][j] = dp[i - 1][j];// 选 A[i-1]if (j > 0 && dp[i - 1][j - 1] != -INF) {long long temp = dp[i - 1][j - 1] * A[i - 1];if (temp > dp[i][j]) {dp[i][j] = temp;}}}}// 输出结果long long result = dp[N][K];if (result < 0) {// 如果结果为负数,按照题目要求处理result = 0 - ((0 - result) % MOD);} else {result %= MOD;}cout << result << endl;return 0;
}

思路如下:

1. 定义状态
  • 设 dp[i][j] 表示从前 i 个数中选出 j 个数,能够得到的最大乘积。

  • 其中:

    • i 表示当前考虑的前 i 个数。

    • j 表示需要选出的数的个数。

2. 状态转移方程

对于每个数 A[i],我们有两种选择:

  1. 不选 A[i]

    • 最大乘积仍然是 dp[i−1][j]。

  2. 选 A[i]

    • 最大乘积是 dp[i−1][j−1]×A[i]。

因此,状态转移方程为:

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−1]×A[i])

3. 初始化
  • dp[0][0]=1:从 0 个数中选出 0 个数,乘积为 1。

  • dp[i][0]=1:从任意 i 个数中选出 0 个数,乘积为 1。

  • dp[0][j]=−∞(无效状态):从 0 个数中选出 j个数是不可能的。

4. 最终结果
  • 我们需要的结果是 dp[N][K],即从前 N 个数中选出 K 个数的最大乘积。

代码解释

  1. 输入处理

    • 读取 N 和 K。

    • 读取数组 A。

  2. 初始化 DP 表

    • dp[i][j] 表示从前 i 个数中选出 j 个数的最大乘积。

    • 初始状态 dp[0][0]=1,其余状态初始化为负无穷(无效状态)。

  3. 状态转移

    • 对于每个数 A[i−1],更新 DP 表。

    • 如果不选 A[i−1],则 dp[i][j]=dp[i−1][j]。

    • 如果选 A[i−1],则 dp[i][j]=dp[i−1][j−1]×A[i−1]。

  4. 结果处理

    • 如果结果为负数,按照题目要求处理。

    • 如果结果为正数,直接取模。

  5. 输出结果

    • 输出最终的最大乘积。


复杂度分析

  • 时间复杂度

    • 动态规划的状态数为 O(N×K),每个状态需要 O(1)时间更新。

    • 总时间复杂度为 O(N×K)。

  • 空间复杂度

    • 需要 O(N×K) 的空间存储 DP 表。

时间复杂度较高,无法通过全部测试点。只有通过贪心和双指针的方法来优化(如上)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35077.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[MAVEN][经验总结]MAVEN_HOME和M2_HOME的配置建议

前言 MAVEN_HOME和M2_HOME都是maven的环境变量&#xff0c;要配置哪个&#xff0c;与maven版本有关&#xff0c;我在实操过程中遇到相关的问题&#xff0c;现记录如下。 MAVEN_HOME和M2_HOME的区别 MAVEN_HOME 和 M2_HOME 本质上是同一个作用的环境变量&#xff0c;它们的区…

力扣Hot100——169. 多数元素

解法1&#xff1a;使用HashMap 将nums数组映射到HashMap中&#xff0c;键为nums的值&#xff0c;值为nums中值的数量&#xff1b; 然后遍历哈希表&#xff0c;返回值最大的键 class Solution {private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Int…

EasyRTC嵌入式音视频通话SDK:微信生态支持、轻量化架构与跨平台兼容性(Linix/Windows/ARM/Android/iOS/LiteOS)

随着WebRTC技术的不断发展&#xff0c;实时音视频通信在各个领域的应用越来越广泛。EasyRTC嵌入式音视频通话SDK作为一款基于WebRTC技术的实时通信解决方案&#xff0c;凭借其强大的功能和灵活的集成能力&#xff0c;受到了越来越多开发者的关注。 一、系统架构设计 纯C语言开…

QuickAPI:一键将 Excel 数据转为数据库表

在开发和数据管理中&#xff0c;将 Excel 数据快速导入数据库是一项常见需求&#xff0c;但手动建表和导入的过程往往让人头疼。 QuickAPI 作为一款高效的统一数据服务平台&#xff0c;提供了一键将 Excel 数据转为数据库表的功能&#xff0c;极大简化了操作流程。本文将以技术…

【MySQL】多表查询(笛卡尔积现象,联合查询、内连接、左外连接、右外连接、子查询)-通过练习快速掌握法

在DQL的基础查询中&#xff0c;我们已经学过了多表查询的一种&#xff1a;联合查询&#xff08;union&#xff09;。本文我们将系统的讲解多表查询。 笛卡尔积现象 首先&#xff0c;我们想要查询emp表和stu表两个表&#xff0c;按照我们之前的知识栈&#xff0c;我们直接使用…

JavaScript如何做类型转换

一、类型转换 二、补充 console.log(1 "2" "2"); // 122 console.log(1 "2" "2"); // 32 console.log(1 -"1" "2"); // 02 console.log("1" "1" "2"); // 112 consol…

华为中小型企业项目案例

实验目的(1) 熟悉华为交换机和路由器的应用场景 (2) 掌握华为交换机和路由器的配置方法 实验拓扑实验拓扑如图所示。 华为中小型企业项目案例拓扑图 实验配置市场部和技术部的配置创建VLANLSW1的配置 [LSW1]vlan batch 10 20 [LSW1]q…

【PyTorch][chapter-35][MLA]

前言&#xff1a; MLA&#xff08;Multi-head Latent Attention&#xff0c;多头潜在注意力&#xff09;旨在提高推理效率和降低计算资源的消。MLA的核心思想在于通过信息转移来优化KV缓存的使用 MLA的技术特点主要包括&#xff1a; KV压缩与潜在变量&#xff1a;将键&#xff…

Spring Cloud 中的服务注册与发现: Eureka详解

1. 背景 1.1 问题描述 我们如果通过 RestTamplate 进行远程调用时&#xff0c;URL 是写死的&#xff0c;例如&#xff1a; String url "http://127.0.0.1:9090/product/" orderInfo.getProductId(); 当机器更换或者新增机器时&#xff0c;这个 URL 就需要相应地变…

微服务存在的问题及解决方案

微服务存在的问题及解决方案 1. 存在问题 1.1 接口拖慢 因为一个接口在并发时&#xff0c;正好执行时长又比较长&#xff0c;那么当前这个接口占用过多的 Tomcat 连接&#xff0c;导致其他接口无法即时获取到 Tomcat 连接来完成请求&#xff0c;导致接口拖慢&#xff0c;甚至…

centos 安装pip时报错 Cannot find a valid baseurl for repo: centos-sclo-rh/x86_64

centos 安装pip时报错 [rootindex-es app-ai]# yum update Loaded plugins: fastestmirror Repository centos-sclo-rh is listed more than once in the configuration Determining fastest mirrors Could not retrieve mirrorlist http://mirrorlist.centos.org?archx86_64…

解决图片转 ICO 图标难题,支持批量处理

还在为图片转 ICO 图标发愁吗&#xff1f;别担心&#xff0c;今天为大家带来一款超实用的工具 ——Any to Icon。它功能强大&#xff0c;可实现批量图片转 ICO 图标&#xff0c;轻松解决格式转换难题。更棒的是&#xff0c;这款工具极为小巧&#xff0c;无需安装&#xff0c;即…

MultiPost--多平台博客发布工具

网站介绍 一键发布内容到多个社交平台的浏览器插件&#xff0c;支持知乎、微博、小红书、抖音等主流平台&#xff0c;支持文字、图片、视频等内容形式. 地址 GitHub &#xff1a; https://github.com/leaper-one/MultiPost-Extension Chorme: https://chromewebstore.google.…

Linux进程状态详解:僵尸进程与孤儿进程的深度探索与实践

文章目录 前言一、进程状态概述1.1 运行状态1.2 阻塞状态1.3 挂起状态 二、具体的Linux操作系统中的进程状态2.1 Linux内核源代码2.2 查看进程状态2.3 D磁盘休眠状态(Disk sleep)D状态的定义&#xff1a; 2.4 T停止状态(stopped)停止状态的概述&#xff1a;停止状态的触发条件&…

【Linux】深入理解进程和文件及内存管理

个人主页~ 深入理解进程和文件及内存管理 一、重谈Linux下一切皆文件二、操作系统对物理内存的管理1、物理内存与磁盘的数据交互2、操作系统对物理内存的管理 三、文件页缓冲区向文件写入数据的过程 四、动态库是如何被加载的关于动态库中的全局变量 五、深入理解地址1、程序地…

★9.4.2 context2D 绘图

返回目录&#xff1a; Qt QML专栏目录结构_qml 项目 目录-CSDN博客 ★9.4.2 context2D 绘图 Object <- context 属性 canvas : QtQuick::Canvas fillRule : enumeration fillStyle : variant fillStyle: 设置或获取当前填充颜色或样式。 font : string g…

汇编基础知识

CPU&#xff1a;一种可以执行机器指令进行运算的芯片&#xff08;微处理器&#xff09;。 存储器&#xff08;内存&#xff09;&#xff1a;存放CPU可以工作的指令和数据&#xff08;指令和数据都是二进制信息&#xff09;。 磁盘不同于内存&#xff0c;磁盘中的数据要读到内…

1536数字三角形

1536数字三角形 ⭐️难度&#xff1a;中等 &#x1f31f;考点&#xff1a;动态规划 &#x1f4d6; &#x1f4da; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;public class Main {public static void main(…

基于VMware的虚拟机集群搭建

本文作者&#xff1a; slience_me 文章目录 基于VMware的虚拟机集群搭建1. 安装Vmware2. 构建虚拟机3. 安装Linux4. 网络配置5. 开始克隆6. 初始化系统6.1 开放root账户6.2 SSH服务6.3 设置静态IP6.4 镜像源 host 主机名 基于VMware的虚拟机集群搭建 该集群采用镜像ubuntu-20.0…

windows平台搭建python环境

python语言 Python 是一种高级、解释型、跨平台的编程语言&#xff0c;由Guido van Rossum于1991年设计&#xff0c;并发展成为全球最受欢迎的编程语言之一。它以简单易读的语法、灵活的特性和丰富的标准库闻名&#xff0c;适合初学者和经验丰富的开发者。 Python 支持多种编…