擅长:python、mysql、java
<p>建议的答案是,首先排序并获取元素,这是不正确的。举一个反例:<code>[2,1,3]</code></p>
<ul>
<li>此问题的解决方案应产生3:<code>(3-1) + (2-1)</code>或
<code>(3-2) + (2-0)</code></li>
<li>然而,建议的解决方案将产生4:<code>(3-1) + (2-0)</code></li>
</ul>
<hr/>
<p>一种可能的(线性时间)解决方案:</p>
<p>让我们从一些代数开始,把绝对值放一分钟</p>
<pre><code>(A[i] – A[j]) + (i – j) = (A[i] + i) - (A[j] + j)
</code></pre>
<p>我们在寻找最大值,所以</p>
<ul>
<li>我们希望最小化<code>(A[j] + j)</code>的值</li>
<li>我们希望最大化<code>(A[i] + i)</code>的价值</李>
<li>请注意,它们彼此完全独立</李>
</ul>
<p>您可以找到两个整数,一个最大化<code>(A[i] + i)</code>,另一个最小化<code>(A[j] + j)</code>。查找这两个数字可以简单地在线性过程中完成</p>
<p>以另一种方式重复(当<code>(A[i] – A[j]) + (i – j)</code>为负时):</p>
<ul>
<li>找到使<code>(A[i] + i)</code>最小化的i</li>
<li>精细的<code>j</code>使<code>(A[j] + j)</code>最大化</李>
</ul>
<p>两者都是在线性时间内完成的,产生<code>O(n)</code>解</p>