s******5 发帖数: 141 | 1 在merge那一步, 如果两个digits相同, 为什么要取后续subarray大的那个?
怎么证明这样会得到最大值? |
s**********g 发帖数: 14942 | 2 如果后面的数字比这个数字大
例如5 8 3 1
那么选择后续数字大的,就可以让你接下来选这个大的数字
例如 5 8 3 1和 5 6 9 0 1,选第一个5让你接下来可以选8,变成58...显然是最优
选第二个5的话,你就没法接上8了,必须跟着再选第一个5才能遇到8,变成558...
如果后面数字不比这个数字大
例如5 4 8 9 和 5 2 9 0 1
那么选择第一个5以后,之后你肯定继续选5,再之后是4 8 9和2 9 0 1相比了。这种情
况下,选哪个5其实没有差别,所以选后续subarray大的肯定好。 |
s******5 发帖数: 141 | 3 谢谢,不过这是一种简单情况。怎么证明更一般的形式呢?比如 5843567 和 5843557
也就是说怎么证明843567merge5843557 大于 5843567merge843557 呢?
【在 s**********g 的大作中提到】 : 如果后面的数字比这个数字大 : 例如5 8 3 1 : 那么选择后续数字大的,就可以让你接下来选这个大的数字 : 例如 5 8 3 1和 5 6 9 0 1,选第一个5让你接下来可以选8,变成58...显然是最优 : 选第二个5的话,你就没法接上8了,必须跟着再选第一个5才能遇到8,变成558... : 如果后面数字不比这个数字大 : 例如5 4 8 9 和 5 2 9 0 1 : 那么选择第一个5以后,之后你肯定继续选5,再之后是4 8 9和2 9 0 1相比了。这种情 : 况下,选哪个5其实没有差别,所以选后续subarray大的肯定好。
|
s**********g 发帖数: 14942 | 4 5abcd..
5abce..
d > e
如果ab...都比5大,c比5小,你绝对会选成5ab 然后就是 cd vs 5abce 和 5abcd vs
ce
此时你绝对会选回5 (因为c小),变成5ab5ab 然后就是cd vs ce
此时选哪个c已经讲过了
如果是更长的序列,那就会交替出现上面的情况,但总之都应该能reduce到基本情形
如果abc都比5大,那么会选成5abc 然后是d vs 5abce (d vs 5) 和 5abcd vs e (5
vs e)
如果5是最大的,那么自然又进入5abc5abc了
如果5不是最大的,那你肯定想接下来选最大的d,所以最初你应该要选5abcd里的5,这
样允许自己到时候可以选d
似乎还有一些edge case,但应该都差不多
总之逻辑就是选择那个能给你机会把更大的数字提前获得的选项
5843557
【在 s******5 的大作中提到】 : 谢谢,不过这是一种简单情况。怎么证明更一般的形式呢?比如 5843567 和 5843557 : 也就是说怎么证明843567merge5843557 大于 5843567merge843557 呢?
|