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

作者:柳行刚

编辑:黄俊嘉

网易的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 条评论
登录 后参与评论

相关文章

来自专栏书山有路勤为径

分治算法之归并排序

分治算法: 将一个规模为N的问题分解为K个规模较小的子问题,这些子问题互相独立且与原问题性质相同。求出子问题的解后进行合并,就可得到原问题的解。

641
来自专栏Python区块链

人工智能实现程序员“防”BOSS?刷脸就发短信,8行代码人脸报警

如今一个攻城狮就能搞定人脸的深度进修算法,这要多感激打动国外开源框架,虽然达不到旷世face++和诸多人脸公司的深度,可是实际应用已经没有太大压力。下图就是te...

45012
来自专栏数据小魔方

R语言学习笔记——R语言面向对象编程系列2

最近在看任坤大神的新作——《R语言编程指南》,其中对于编程语言中非常流行的面向对象编程范式(OOP)在R语言中的实现进行了非常详尽的讲解,强烈推荐各位有志于进阶...

32212
来自专栏C/C++基础

C++0x 通用属性

C++在不断的发展,但每一阶段的C++标准提供的功能都很难完全满足现实需求,于是为了弥补标准的不足或者扩增特性应用场景所需的特性,各大C++编译器厂商多多少少在...

1002
来自专栏SimpleAI

Python高级特性——为什么都说Python高效

本微教程根据廖雪峰python教程中的部分内容,配合我个人的学习经历进行总结整理。

1034
来自专栏ACM算法日常

I Hate It!(线段树-超详细~)- HDU 1754

很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢,现在需要你做的是,就是按照老师的要求...

782
来自专栏Crossin的编程教室

这些年,你们一起踩过的坑(2)

上次我们踩坑总结文章 这些年,你们一起踩过的坑(1) 受到了不少同学的认可。我也确信文中所涉及的问题是非常具有普遍性的,对绝大多数初学者都会有帮助。

1003
来自专栏Python小屋

Python使用递归对任意嵌套列表进行扁平化

首先补充一个地方,之前有个文章演示的是猜数游戏,原文链接为猜数游戏用Python应该这样写,代码中漏掉了一个break语句,也就是说,在猜对的时候输出语句pri...

3428
来自专栏AI派

Numpy 修炼之道 (13)—— 将python函数向量化

想要实现将python函数向量化,Numpy中的vectorize 和frompyfunc函数都可以满足要求。

3777
来自专栏算法channel

程序员必知的算法和数据结构:2500字性能总结

以下5个步骤总结了此方法,依次为如下,我们设计的实验必须是可以重现的,我们形成的假设必须是具有真伪的。

670

扫码关注云+社区