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 呢？
|
