请教一个数组题 - 未名空间MITBBS历史存档

c*02011-09-26 07:09

1 楼

Given a sorted array of n integers, pick up k elements so that the minimal
difference between consecutive elements is maximal (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))

g*y2011-09-26 07:09

2 楼

Sliding window maximum problem的变形：
http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

【在 c********0 的大作中提到】

: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximal (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))

s*j2011-09-26 07:09

3 楼

dp
f[i][j] means when have already chosen i numbers and the last chosen number
is a[j], the maximum minimum difference

k*n2011-09-26 07:09

4 楼

this is nothing related to sliding window

【在 g**********y 的大作中提到】

: Sliding window maximum problem的变形：
: http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

c*02011-09-26 07:09

5 楼

火鸡可以给解释下不？

【在 g**********y 的大作中提到】

: Sliding window maximum problem的变形：
: http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

c*02011-09-26 07:09

6 楼

number
then how do you update? f[i+1][j] = ?

【在 s****j 的大作中提到】

: dp
: f[i][j] means when have already chosen i numbers and the last chosen number
: is a[j], the maximum minimum difference

g*y2011-09-26 07:09

7 楼

对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
这个计算跟sliding window maximum是大同小异的。
如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

【在 c********0 的大作中提到】

:
: number
: then how do you update? f[i+1][j] = ?

c*02011-09-26 07:09

8 楼

Thanks! 题目确实是任意k个数

【在 g**********y 的大作中提到】

: 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
: 数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
: 变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
: 这个计算跟sliding window maximum是大同小异的。
: 如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

d*d2011-09-26 07:09

9 楼

火鸡，这题应该不是这个意思。

【在 g**********y 的大作中提到】

: 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
: 数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
: 变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
: 这个计算跟sliding window maximum是大同小异的。
: 如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

H*s2011-09-26 07:09

10 楼

相邻数之间的差存一个数组 O(n)
然后再选择最大的k个差值 O(n)
总复杂度O(n)

g*y2011-09-26 07:09

11 楼

对任意k个数，就象songlj说的，DP。

【在 c********0 的大作中提到】

:
: Thanks! 题目确实是任意k个数

H*s2011-09-26 07:09

12 楼

Ok, 我也理解错题目了，是选出的数中maximum minimum difference

g*i2011-09-26 07:09

13 楼

dp复杂度高
我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
nlog(Max(a[i])))

r*g2011-09-26 07:09

14 楼

是的，感觉更像你说的，先排序，然后类似paint partition problem, 1337上面有解
法。
貌似不是sliding window

【在 g*****i 的大作中提到】

: dp复杂度高
: 我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
: nlog(Max(a[i])))

c*12011-09-26 07:09

15 楼

怎么binary search啊。。。感觉很飘渺啊

【在 r*******g 的大作中提到】

: 是的，感觉更像你说的，先排序，然后类似paint partition problem, 1337上面有解
: 法。
: 貌似不是sliding window

r*g2011-09-26 07:09

16 楼

http://www.ihas1337code.com/2011/04/the-painters-partition-prob
你这个题目，其实就是做k partition, 然后要maximize the minimum, 而paint
partition problem是要minimize the maximum，根据他的dp方法应该是可解的。
关于binary search，你要search的就是minimum的值，它最小是目前最小的partition,最大是整个
长度，这个值如果过大，那么k个parition总长度就会超过整个长度。
http://www.ihas1337code.com/2011/04/the-painters-partition-prob

【在 c********1 的大作中提到】

:
: 怎么binary search啊。。。感觉很飘渺啊

c*12011-09-26 07:09

17 楼

partition,最大是整个
我觉得我没把问题讲清楚。。。这个不是partition的问题
比如说给一个数组 [1,4,6,7] k = 2
那么我们选1和7就是最优的因为差是6最大
如果k=3我们选1，4，7
差是3 (maximize the minimal difference)

【在 r*******g 的大作中提到】

: http://www.ihas1337code.com/2011/04/the-painters-partition-prob
: 你这个题目，其实就是做k partition, 然后要maximize the minimum, 而paint
: partition problem是要minimize the maximum，根据他的dp方法应该是可解的。
: 关于binary search，你要search的就是minimum的值，它最小是目前最小的partition,最大是整个
: 长度，这个值如果过大，那么k个parition总长度就会超过整个长度。
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob

g*y2011-09-26 07:09

18 楼

Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;

int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;

while (hi > lo+1) {
int mid = (hi + lo) / 2;
if (test(a, mid, k)) {
lo = mid;
}
else {
hi = mid;
}
}

return lo;
}

private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; iwhile (jif (j >= a.length) return false;
prev = a[j];
}
return true;
}
}

【在 c********1 的大作中提到】

:
: partition,最大是整个
: 我觉得我没把问题讲清楚。。。这个不是partition的问题
: 比如说给一个数组 [1,4,6,7] k = 2
: 那么我们选1和7就是最优的因为差是6最大
: 如果k=3我们选1，4，7
: 差是3 (maximize the minimal difference)

B*12011-09-26 07:09

19 楼

这样子求出来的序列似乎一定要从index 0 开始的
是吗？
private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; iwhile (jif (j >= a.length) return false;
prev = a[j];
}
return true;
}

【在 g**********y 的大作中提到】

: Java code =>
: public class MaxMinDiff {
: public int max(int[] a, int k) {
: int N = a.length;
: if (N < k || k < 2) return -1;
:
: int lo = 0;
: int hi = (a[N-1] - a[0]) / (k-1) + 1;
:
: while (hi > lo+1) {

g*y2011-09-26 07:09

20 楼

It's sorted array. There must be an optimum solution start with a0, end with
a(n-1)

【在 B*******1 的大作中提到】

: 这样子求出来的序列似乎一定要从index 0 开始的
: 是吗？
: private boolean test(int[] a, int diff, int k) {
: int prev = a[0];
: int j = 1;
: for (int i=1; i: while (j: if (j >= a.length) return false;
: prev = a[j];
: }

B*12011-09-26 07:09

21 楼

thanks，现在懂了，这个发现是解这题的关键。其实你的方法跟这哥们的一样
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri

with

【在 g**********y 的大作中提到】

: It's sorted array. There must be an optimum solution start with a0, end with
: a(n-1)

c*12011-09-26 07:09

22 楼

Good one, thanks!

【在 g**********y 的大作中提到】

: Java code =>
: public class MaxMinDiff {
: public int max(int[] a, int k) {
: int N = a.length;
: if (N < k || k < 2) return -1;
:
: int lo = 0;
: int hi = (a[N-1] - a[0]) / (k-1) + 1;
:
: while (hi > lo+1) {

r*g2011-09-26 07:09

23 楼

这个其实就是partition问题，排序后对最大和最小的差值进行分段，如何选择分段的
问题，code已经有人贴出来了。

【在 c********1 的大作中提到】

:
: Good one, thanks!

c*02011-09-26 07:09

24 楼

Given a sorted array of n integers, pick up k elements so that the minimal
difference between consecutive elements is maximal (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))

g*y2011-09-26 07:09

25 楼

Sliding window maximum problem的变形：
http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

【在 c********0 的大作中提到】

: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximal (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))

s*j2011-09-26 07:09

26 楼

dp
f[i][j] means when have already chosen i numbers and the last chosen number
is a[j], the maximum minimum difference

k*n2011-09-26 07:09

27 楼

this is nothing related to sliding window

【在 g**********y 的大作中提到】

: Sliding window maximum problem的变形：
: http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

c*02011-09-26 07:09

28 楼

火鸡可以给解释下不？

【在 g**********y 的大作中提到】

: Sliding window maximum problem的变形：
: http://www.ihas1337code.com/2011/01/sliding-window-maximum.html

c*02011-09-26 07:09

29 楼

number
then how do you update? f[i+1][j] = ?

【在 s****j 的大作中提到】

: dp
: f[i][j] means when have already chosen i numbers and the last chosen number
: is a[j], the maximum minimum difference

g*y2011-09-26 07:09

30 楼

对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
这个计算跟sliding window maximum是大同小异的。
如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

【在 c********0 的大作中提到】

:
: number
: then how do you update? f[i+1][j] = ?

c*02011-09-26 07:09

31 楼

Thanks! 题目确实是任意k个数

【在 g**********y 的大作中提到】

: 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
: 数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
: 变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
: 这个计算跟sliding window maximum是大同小异的。
: 如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

d*d2011-09-26 07:09

32 楼

火鸡，这题应该不是这个意思。

【在 g**********y 的大作中提到】

: 对你的题目，我的理解是：找连续的k个数，最大化他们的最小邻近差值。
: 数组的邻近差值是固定的，所以你可以计算出新数组b[], b[i]=a[i+1]-a[i]。题目就
: 变成了，在数组b里，找size=k-1的窗口，最大化窗口里的最小数。
: 这个计算跟sliding window maximum是大同小异的。
: 如果你的题目是任意的k个数，最大化最小邻近差值，解法就不一样了。

H*s2011-09-26 07:09

33 楼

相邻数之间的差存一个数组 O(n)
然后再选择最大的k个差值 O(n)
总复杂度O(n)

g*y2011-09-26 07:09

34 楼

对任意k个数，就象songlj说的，DP。

【在 c********0 的大作中提到】

:
: Thanks! 题目确实是任意k个数

H*s2011-09-26 07:09

35 楼

Ok, 我也理解错题目了，是选出的数中maximum minimum difference

g*i2011-09-26 07:09

36 楼

dp复杂度高
我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
nlog(Max(a[i])))

r*g2011-09-26 07:09

37 楼

是的，感觉更像你说的，先排序，然后类似paint partition problem, 1337上面有解
法。
貌似不是sliding window

【在 g*****i 的大作中提到】

: dp复杂度高
: 我觉得这题类似paint partition problem,应该用binary search,复杂度是O(nlogn+
: nlog(Max(a[i])))

c*12011-09-26 07:09

38 楼

怎么binary search啊。。。感觉很飘渺啊

【在 r*******g 的大作中提到】

: 是的，感觉更像你说的，先排序，然后类似paint partition problem, 1337上面有解
: 法。
: 貌似不是sliding window

r*g2011-09-26 07:09

39 楼

http://www.ihas1337code.com/2011/04/the-painters-partition-prob
你这个题目，其实就是做k partition, 然后要maximize the minimum, 而paint
partition problem是要minimize the maximum，根据他的dp方法应该是可解的。
关于binary search，你要search的就是minimum的值，它最小是目前最小的partition,最大是整个
长度，这个值如果过大，那么k个parition总长度就会超过整个长度。
http://www.ihas1337code.com/2011/04/the-painters-partition-prob

【在 c********1 的大作中提到】

:
: 怎么binary search啊。。。感觉很飘渺啊

c*12011-09-26 07:09

40 楼

partition,最大是整个
我觉得我没把问题讲清楚。。。这个不是partition的问题
比如说给一个数组 [1,4,6,7] k = 2
那么我们选1和7就是最优的因为差是6最大
如果k=3我们选1，4，7
差是3 (maximize the minimal difference)

【在 r*******g 的大作中提到】

: http://www.ihas1337code.com/2011/04/the-painters-partition-prob
: 你这个题目，其实就是做k partition, 然后要maximize the minimum, 而paint
: partition problem是要minimize the maximum，根据他的dp方法应该是可解的。
: 关于binary search，你要search的就是minimum的值，它最小是目前最小的partition,最大是整个
: 长度，这个值如果过大，那么k个parition总长度就会超过整个长度。
: http://www.ihas1337code.com/2011/04/the-painters-partition-prob

g*y2011-09-26 07:09

41 楼

Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;

int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;

while (hi > lo+1) {
int mid = (hi + lo) / 2;
if (test(a, mid, k)) {
lo = mid;
}
else {
hi = mid;
}
}

return lo;
}

private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; iwhile (jif (j >= a.length) return false;
prev = a[j];
}
return true;
}
}

【在 c********1 的大作中提到】

:
: partition,最大是整个
: 我觉得我没把问题讲清楚。。。这个不是partition的问题
: 比如说给一个数组 [1,4,6,7] k = 2
: 那么我们选1和7就是最优的因为差是6最大
: 如果k=3我们选1，4，7
: 差是3 (maximize the minimal difference)

B*12011-09-26 07:09

42 楼

这样子求出来的序列似乎一定要从index 0 开始的
是吗？
private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; iwhile (jif (j >= a.length) return false;
prev = a[j];
}
return true;
}

【在 g**********y 的大作中提到】

: Java code =>
: public class MaxMinDiff {
: public int max(int[] a, int k) {
: int N = a.length;
: if (N < k || k < 2) return -1;
:
: int lo = 0;
: int hi = (a[N-1] - a[0]) / (k-1) + 1;
:
: while (hi > lo+1) {

g*y2011-09-26 07:09

43 楼

It's sorted array. There must be an optimum solution start with a0, end with
a(n-1)

【在 B*******1 的大作中提到】

: 这样子求出来的序列似乎一定要从index 0 开始的
: 是吗？
: private boolean test(int[] a, int diff, int k) {
: int prev = a[0];
: int j = 1;
: for (int i=1; i: while (j: if (j >= a.length) return false;
: prev = a[j];
: }

B*12011-09-26 07:09

44 楼

thanks，现在懂了，这个发现是解这题的关键。其实你的方法跟这哥们的一样
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri

with

【在 g**********y 的大作中提到】

: It's sorted array. There must be an optimum solution start with a0, end with
: a(n-1)

c*12011-09-26 07:09

45 楼

Good one, thanks!

【在 g**********y 的大作中提到】

: Java code =>
: public class MaxMinDiff {
: public int max(int[] a, int k) {
: int N = a.length;
: if (N < k || k < 2) return -1;
:
: int lo = 0;
: int hi = (a[N-1] - a[0]) / (k-1) + 1;
:
: while (hi > lo+1) {

r*g2011-09-26 07:09

46 楼

这个其实就是partition问题，排序后对最大和最小的差值进行分段，如何选择分段的
问题，code已经有人贴出来了。

【在 c********1 的大作中提到】

:
: Good one, thanks!

k*t2011-09-26 07:09

47 楼

Isn't test() function use Greedy approach?
Can some one explain the reason why the greedy algorithm work?
Any link to algorithm explanation?

附Link上火鸡的Code:
Java code =>
public class MaxMinDiff {
public int max(int[] a, int k) {
int N = a.length;
if (N < k || k < 2) return -1;

int lo = 0;
int hi = (a[N-1] - a[0]) / (k-1) + 1;

while (hi > lo+1) {
int mid = (hi + lo) / 2;
if (test(a, mid, k)) {
lo = mid;
}
else {
hi = mid;
}
}

return lo;
}

private boolean test(int[] a, int diff, int k) {
int prev = a[0];
int j = 1;
for (int i=1; iwhile (jif (j >= a.length) return false;
prev = a[j];
}
return true;
}

【在 g**********y 的大作中提到】

: Java code =>
: public class MaxMinDiff {
: public int max(int[] a, int k) {
: int N = a.length;
: if (N < k || k < 2) return -1;
:
: int lo = 0;
: int hi = (a[N-1] - a[0]) / (k-1) + 1;
:
: while (hi > lo+1) {

H*e2011-09-26 07:09

48 楼

要是真面试就用DP了
思路比较清晰
我还是觉得binary search的有些疑问。。

【在 c********0 的大作中提到】

: Given a sorted array of n integers, pick up k elements so that the minimal
: difference between consecutive elements is maximal (that is choose the
: elements to maximize the quantity min(a[i+1] - a[i]))