一道网易笔试题引发的血案……

作者:柳行刚

编辑:黄俊嘉

网易的2016年笔试题,题目经典。

所以特地找来给各位有兴趣的童鞋看看,

有详细的解题思路以及代码喔~

各位,请看题!

题目描述:

有 n 个学生站成一排,每个学生有一个能力值,牛牛想从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能力值的乘积最大,你能返回最大的乘积吗?

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50),表示学生的个数,接下来的一行,包含 n 个整数,按顺序表示每个学生的能力值 ai(-50 <= ai <= 50)。接下来的一行包含两个整数,k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述:

输出一行表示最大的乘积。

输入例子:

输出例子:

思路分析

这是一个动态规划问题,需要找到状态转移方程。假设maxval[i][j]表示以第i个人结束,且i前面被选中j个人时的最大乘积(此时被选中的共有j+1个人),minval[i][j]表示相同情况下的最小乘积。则maxval[i][j]与maxval[i][j]本身以及maxval[t][j-1]*a[i]、minval[t][j-1]*a[i]有关(t=i-d~i-1)。这里之所以要考虑minval[t][j-1],是因为min[t][j-1]可能为一个很小的负数,而a[i]也是一个很小的负数,二者相乘就会很大。

maxval[i][j]=max(maxval[i][j],

max(maxval[t][j-1]*a[i], minval[t][j-1]*a[i]));

minval[i][j]=min(minval[i][j],

min(maxval[t][j-1]*a[i], minval[t][j-1]*a[i]));

最后在maxval[i][k-1]里求最大值即可。

具体代码

C++:

(点开大图,可详细清晰地看代码)

Python:

不知各位同学有没有理解清楚,倘若没有理解清楚,可以在留言板留言,也可以添加群,直接问柳老师喔,同时还有很多业内大牛在里面~

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

简单理解倒排索引

倒排索引从逻辑结构和基本思路上来讲非常简单。下面我们通过具体实例来进行说明,使得读者能够对倒排索引有一个宏观而直接的感受。假设文档集合包含五个文档,每个文档内容...

622
来自专栏逆向技术

逆向知识十三讲,汇编中数组的表现形式,以及还原数组

            逆向知识十三讲,汇编中数组的表现形式,以及还原数组 讲解数组之前,要了解数组的特性 1.数据具有连续性 2.数据类型相同 比如:   i...

1837
来自专栏落影的专栏

程序员进阶之算法练习(十四)

前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

3347
来自专栏游戏开发那些事

【游戏开发】小白学Lua(上)

  在很多游戏中,脚本语言是不可或缺的一部分,很多游戏都使用到了Lua,js,python一类的脚本,脚本语言可以在很多方面给开发进程带来帮助。脚本语言可以作为...

732
来自专栏鹅厂优文

深入浅出Lua虚拟机

本文标题是”深入浅出 Lua 虚拟机”,其实重点在浅出这两字上。毕竟作者的技术水平有限。但是听说名字要起的屌一点文章才有人看,故而得名。

86314
来自专栏机器学习算法全栈工程师

红黑树算法

前情提要 红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下...

36312
来自专栏小文博客

蓝桥杯 C语言省赛 习题3 移动距离

1166
来自专栏窗户

平方根的C语言实现(三) ——最终程序实现

  了解了浮点数的存储以及手算平方根的原理,我们可以考虑程序实现了。   先实现一个64位整数的平方根,根据之前的手算平方根,程序也不是那么难写了。 #incl...

2078
来自专栏null的专栏

挑战数据结构和算法——栈的push、pop序列

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 问题分析:本题考查栈的基本操作,栈是一种“先进后出”的数据结构。判...

2946
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

3267

扫码关注云+社区