擅长:python、mysql、java
<p>有很多算法,取决于你想要什么。通常他们需要跟踪部分和。如果只保留和x[k+1]-x[k],就得到Kahan算法。如果你跟踪所有的部分和(因此产生O(n^2)算法),你会得到@dF的答案。</p>
<p>请注意,除了您的问题之外,将不同符号的数目相加是非常有问题的。</p>
<p>现在,有比跟踪所有部分和更简单的方法:</p>
<ul>
<li>在求和之前对数字进行排序,对所有的负数和正数进行独立求和。如果你有排序的数字,很好,否则你有O(n logn)算法。通过增加幅度求和。</li>
<li>先成对求和,然后成对求和,等等</li>
</ul>
<p>个人经验表明,你通常不需要比卡恩的方法更华丽的东西。</p>