Facebook:Convert it to a sorted array with minimum cost.

You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element

For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3

You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element

For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3
Imbalism 发表于 2011-10-9 07:49

这题我以前发过, 这题太难了, 我放弃, 怎么最近在准备facebook?

回复 2# wwwyhx


Interview in next week ...

好像离散化加DP可以做，不过很麻烦。另外LZ面试加油，除了算法，熟悉下facebook网站及相关技术或许会有帮助。。