f*********i
发帖数: 197 | 1 求一个unsorted数组中最长的等差数列（int 数组，可递增或者递减）
如果是求unsorted的最长递增或者递减串，那么是有一个nlogn的方法，加上等差这个
条件，估计要是n2了。
我在想是不是一开始可以用动态规划的方法，创建几个数组A和B，假设原始数组为C,那
么Ai是Ci左边第一个比Ci小的数，Bi是Ci又变第一个比Ci大的数，然后通过这两个辅助
函数查找。
好像到这里就卡住了，有没有高人给个解法我？ |
g**********y
发帖数: 14569 | 2 等差数列在原数组里是连续的，还是可以不连续的？
【在 f*********i 的大作中提到】
: 求一个unsorted数组中最长的等差数列（int 数组，可递增或者递减）
: 如果是求unsorted的最长递增或者递减串，那么是有一个nlogn的方法，加上等差这个
: 条件，估计要是n2了。
: 我在想是不是一开始可以用动态规划的方法，创建几个数组A和B，假设原始数组为C,那
: 么Ai是Ci左边第一个比Ci小的数，Bi是Ci又变第一个比Ci大的数，然后通过这两个辅助
: 函数查找。
: 好像到这里就卡住了，有没有高人给个解法我？
|
g*****k
发帖数: 623 | 3 连续的太简单了吧。应该是不连续的序列吧。
【在 g**********y 的大作中提到】
: 等差数列在原数组里是连续的，还是可以不连续的？
|
a********m
发帖数: 15480 | 4 测试前两个数字的差，然后用这个差继续往后测试。遇到不同差把开始指针跳到这两个
数字重复就可以了吧？这样o(n)扫描一遍就完了。 |
a********m
发帖数: 15480 | 5 不过这个是最简单的情况。如果要求不连续就复杂多了。
【在 a********m 的大作中提到】
: 测试前两个数字的差，然后用这个差继续往后测试。遇到不同差把开始指针跳到这两个
: 数字重复就可以了吧？这样o(n)扫描一遍就完了。
|
s******c
发帖数: 1920 | |
g**********y
发帖数: 14569 | 7 赞！这么看，O(n^2)几乎就是极限了。再进一步，可以发文章了。
【在 s******c 的大作中提到】
: 网上有个O(n^2)的算法，需要先排序和剔除重复。
: http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
|
g**********y
发帖数: 14569 | 8 我看到这种问题经常在想：interview半个小时就给出几乎可以发paper的解，如果从来
没见过，这得是多牛的人啊？
还是公司就只招那种：“熬着通红的双眼，拿着paper去找教授抱怨，昨天的家庭作业
太难了！原来一不小心解了个困扰业界25年的问题" |
