这个推论的初衷是为了优化某题的时间复杂度,但不知怎么的脑子混沌,推不下去了。(虽然真的很简单)
给一个长度n的数列
|(a1-an)|+|(a2-an−1)|+|(a3-an−2)|+……+|(a(1+n)/2-a(1+n)/2)|……
我们拆括号,应该是:
|a1-an|+|a2-an−1|+|a3-an−2|+……+|a(1+n)/2-a(1+n)/2|
这个时候,我们可以清楚的发现,a1,a2,a3这些数可以合并起来,变成a1+a2+a3。an,an−1,an−2也可以合并起来,变成an-an−1-an−2。
于是乎,就变成|(a1+a2+a3+……+a(1+n)/2)|-|(an+an−1+an−2+……+a(1+n)/2)|,两边都出现了a(1+n)/2,抵消成|(a1+a2+a3+……+a(1+n)/2−1)|-|(an+an−1+an−2+……+a(1+n)/2+1)|
这样子对吗?(处于脑子不正常状态下推出这个结论的我)
这样是可以举出反例的。
如n=5时,数列为4、1、3、9、2。
|4-2|+|1-9|+|3-3|=10
而按照我的推论,应为|(4+1)|-|(9+2)|=6
嗨嗨嗨,推错了。
那,正确应该怎么推呢?(本人5年级,当时脑子混沌,哪里写错了勿喷)