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

作者:柳行刚

编辑:黄俊嘉

网易的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一日一条

谈谈 Hash Table

结构体(或对象)可以是基本数据类型或者其他结构体(或对象)的组合。结构体或对象一般用来描述一个复杂数据实体。

432
来自专栏AI派

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

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

3567
来自专栏iKcamp

翻译连载 | 附录 A:Transducing(上)-《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 JavaScript 轻量级函数...

1938
来自专栏tkokof 的技术,小趣及杂念

位运算实用指南

说明 : 想来这应该是初次接触移位操作符时一定会了解到的知识点,根据2进制的整数表示方法应该不难理解,原因细节不再赘述~

541
来自专栏ACM算法日常

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

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

762
来自专栏机器学习算法与Python学习

Python中的实用小技巧

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 话说python是一个大杂会,既可以...

3275
来自专栏Crossin的编程教室

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

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

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

HUST 1588 辗转数对

1588 - 辗转数对 时间限制:1秒 内存限制:128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b),我们可以通过一步将这个数对...

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

51Nod 1182 完美字符串(字符串处理 贪心 Facebook Hacker Cup选拔)

1182 完美字符串 ?             题目来源:                         Facebook Hacker Cup选拔    ...

2757
来自专栏算法修养

接口和多态性

如果你又加了一个百度外卖,那么eat函数中又要new 一个BaiDu() ,给开发带来麻烦。我们希望的是,如果代码要扩展了,那么代码要尽最大可能的进行很小的改动...

803

扫码关注云+社区