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

作者:柳行刚

编辑:黄俊嘉

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

相关文章

来自专栏WD学习记录

牛客网 合唱团

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

632
来自专栏搜云库

《十大经典排序算法》简介

十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的...

1776
来自专栏诸葛青云的专栏

C语言for语句用法详解

在C语言中,for语句使用最为灵活,它完全可以取代 while 语句。它的一般形式为:

20
来自专栏深度学习与计算机视觉

算法-1到n中所有和为m的组合

题目: 输入两个整数 n 和 m,从数列1,2,3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来。 解题思路: 好未来笔试题...

1925
来自专栏AI派

如何使用Python颠倒是非黑白?

有没有发现,打印 True 结果是 False,打印 False 结果是 True。是非黑白就在这么一瞬间颠倒了

451
来自专栏编程

关于正则表达式的5个小贴士

正则表达式是一个非常强大的处理字符工具,但有时可读性很差、晦涩难懂,Jamie Zawinski 说道: Some people, when confronte...

1728
来自专栏我的博客

快速排序

思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排...

2675
来自专栏racaljk

clang -O3 for循环的LLVM IR

这里删去了用处不大的内容,只保留了关键的LLVM IR。通过分析可以看到,如果循环小于8 LLVM IR会使用vector,vector使用SIMD指令高效进行...

903
来自专栏数据结构与算法

07:机器翻译

7:机器翻译 总时间限制: 1000ms 内存限制: 65536kB描述 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 这个翻译软件...

3786
来自专栏数据结构与算法

P1423 小玉在游泳

题目描述 小玉开心的在游泳,可是她很快难过的发现,自己的力气不够,游泳好累哦。已知小玉第一步能游2米,可是随着越来越累,力气越来越小,她接下来的每一步都只能游出...

2415

扫描关注云+社区