牛客网编程挑战赛第二场-英雄不问出处，看看你能做对几题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3543 天前的主题，其中的信息可能已经有所发展或是发生改变。

18:30-21:30,三小时，三个题，等你来战！

戳-> http://www.nowcoder.com/contest/6091/summary

第 1 条附言 · 2015-03-12 19:15:51 +08:00

如果不需要实习内推可以随便填写姓名参加～多谢支持

不问

编程

挑战赛

4 条回复 • 2015-03-13 09:16:59 +08:00

zhujinliang

2015-03-12 21:41:44 +08:00

第一题
搜索最大值，记为max，然后取 abs(max - vec[0]) 与 abs(max - vec[len-1]) 中值大的那个
即只有两种分法，左arr[0..0] 右arr[1..length-1] 或左arr[0..length-2] 右 [length-1..length-1]

第三题根本没思路。。。哪位能否给讲讲。。

nowcoder

2015-03-12 22:22:34 +08:00

@zhujinliang 对的，第一题这是最优解 O(N)搞定

bobai

2015-03-12 23:59:51 +08:00

@nowcoder 分出left，right之后collection.max(left)-colleciton.max(right) 或 collection.max(right)-colleciton.max(left) 这种呢？

nowcoder

2015-03-13 09:16:59 +08:00

@bobai 也可以，但是这个复杂度@zhujinliang 要高。他的算法是最优的