算法笔试模拟题精解之“小明的数学作业”

简介: 关键在于对题目的了解,数学老师让小明求的是n个数中最长的等差数列长度,可以用dp[i][j]表示以a[j]和a[i]为结尾的等差序列的最长长度。

在线编程介绍

阿里云开发者社区在线编程产品,针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等,界面整洁明了,操作简单,为用户营造专心答题的学习环境。点击链接开始体验:https://developer.aliyun.com/coding

本文为大家介绍其中的 129题:小明的数学作业,具体如下:

题目描述

等级:容易
知识点:DP、尺取法
查看题目:小明的数学作业

众所周知,小明是一个数学小能手,有一天数学老师给了小明一个长度为n(2<=n<=5000)的序列,其中第i个数是ai(0<=ai<=1e9),数学老师想知道这个序列排序后,其中最长的等差子序列的长度是多长,聪明的你能帮小明解决这个问题吗?

其中等差子序列的定义为:一个长度为length的等差序列b1、b2……blength,并且序列b是序列a排序后的子序列。

请注意子序列的定义:在原来序列中找出任意数量,任意位置的元素,在不调换这些选出的元素前后顺序的情况下,组成的新序列,称为原序列的子序列。

第一行为序列的长度n(2<=n<=5000),接下来一行是n个数,其中第i个数是ai(0<=ai<=1e9)。

输出一行,最长的等差子序列b的长度length。

示例1
输入:
6
[0,1,3,5,6,9]
输出:
4

解题思路:

首先来理解一下题目:数学老师让小明求的是n个数中最长的等差数列长度,可以用dpi表示以a[j]和a[i]为结尾的等差序列的最长长度。

因为我们肯定要保存一个公差作为状态量,但是直接枚举0-1e9又不现实。

所以我们巧妙的设计出了这个状态,使得我们的公差就被a[i]-a[j]表示了。

因此我们的转移就应该是在三个数中转移。 即a[i],a[j],a[k],i根据等差数列的性质,若a[i],a[j],a[k]构成等差序列,那么a[i]+a[k]=2*a[j];每次转移更新答案即可。

是不是有思路了呢,点击链接立刻答题:>>查看题目:129.小明的数学作业

另有在线编程3月份比赛正式开启!机械键盘等你拿!

893-90-1.jpg

相关文章
|
29天前
|
机器学习/深度学习 算法 Java
基于灰狼优化算法(GWO)解决柔性作业车间调度问题(Matlab代码实现)
基于灰狼优化算法(GWO)解决柔性作业车间调度问题(Matlab代码实现)
117 1
|
29天前
|
供应链 算法 Java
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 人工智能 算法
当AI提示词遇见精密算法:TimeGuessr如何用数学魔法打造文化游戏新体验
TimeGuessr融合AI与历史文化,首创时间与空间双维度评分体系,结合分段惩罚、Haversine距离计算与加权算法,辅以连击、速度与完美奖励机制,实现公平且富挑战性的游戏体验。
|
1月前
|
供应链 算法 调度
基于非支配吸血水蛭优化算法 (NSBSLO)求解多目标柔性作业车间调度问题(FJSP)研究(Matlab代码实现)
基于非支配吸血水蛭优化算法 (NSBSLO)求解多目标柔性作业车间调度问题(FJSP)研究(Matlab代码实现)
|
26天前
|
机器学习/深度学习 负载均衡 算法
【柔性作业车间调度】基于四种多目标优化算法(NSOOA、NSPSO、NSDBO、NSCOA)求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度】基于四种多目标优化算法(NSOOA、NSPSO、NSDBO、NSCOA)求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
106 0
|
7月前
|
算法 数据可视化 调度
基于NSGAII的的柔性作业调度优化算法MATLAB仿真,仿真输出甘特图
本程序基于NSGA-II算法实现柔性作业调度优化,适用于多目标优化场景(如最小化完工时间、延期、机器负载及能耗)。核心代码完成任务分配与甘特图绘制,支持MATLAB 2022A运行。算法通过初始化种群、遗传操作和选择策略迭代优化调度方案,最终输出包含完工时间、延期、机器负载和能耗等关键指标的可视化结果,为制造业生产计划提供科学依据。
|
8月前
|
机器学习/深度学习 算法
扩散模型=进化算法!生物学大佬用数学揭示本质
在机器学习与生物学交叉领域,Tufts和Harvard大学研究人员揭示了扩散模型与进化算法的深刻联系。研究表明,扩散模型本质上是一种进化算法,通过逐步去噪生成数据点,类似于进化中的变异和选择机制。这一发现不仅在理论上具有重要意义,还提出了扩散进化方法,能够高效识别多解、处理高维复杂参数空间,并显著减少计算步骤,为图像生成、视频合成及神经网络优化等应用带来广泛潜力。论文地址:https://arxiv.org/pdf/2410.02543。
228 21
|
9月前
|
机器学习/深度学习 算法 PyTorch
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
软演员-评论家算法(Soft Actor-Critic, SAC)是深度强化学习领域的重要进展,基于最大熵框架优化策略,在探索与利用之间实现动态平衡。SAC通过双Q网络设计和自适应温度参数,提升了训练稳定性和样本效率。本文详细解析了SAC的数学原理、网络架构及PyTorch实现,涵盖演员网络的动作采样与对数概率计算、评论家网络的Q值估计及其损失函数,并介绍了完整的SAC智能体实现流程。SAC在连续动作空间中表现出色,具有高样本效率和稳定的训练过程,适合实际应用场景。
2681 7
深度强化学习中SAC算法:数学原理、网络架构及其PyTorch实现
|
9月前
|
机器学习/深度学习 人工智能 算法
Transformer打破三十年数学猜想!Meta研究者用AI给出反例,算法杀手攻克数学难题
《PatternBoost: Constructions in Mathematics with a Little Help from AI》提出了一种结合传统搜索算法和Transformer神经网络的PatternBoost算法,通过局部搜索和全局优化交替进行,成功应用于组合数学问题。该算法在图论中的Ramsey数研究中找到了更小的反例,推翻了一个30年的猜想,展示了AI在数学研究中的巨大潜力,但也面临可解释性和通用性的挑战。论文地址:https://arxiv.org/abs/2411.00566
211 13
|
11月前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。

热门文章

最新文章