c是给定的n整数数组；问题是找到一个递增的n整数数组，以a (a[i] <= a[i+1])使这个总和最小化：
abs(a[0]+c[0]) + abs(a[1]+c[1]) + ... + abs(a[n-1]+c[n-1])
// abs(x) = absolute value of x
最优a存在仅由出现的整数构成，c因此我们可以使用 DP in 解决它O(n^2)：
dp[i][j]: a[i] >= j'th integer
但是应该有一个更快的解决方案，可能O(n lg n)。
更新：我添加了解决方案，它最小化了绝对值的总和。其他最小化平方和的解决方案仍然在这里，在这篇文章的末尾，以防有人感兴趣。
我从算法开始，它只适用于非负整数数组。然后它将扩展到任何整数（甚至扩展到非整数对象）。
这是一个贪心算法。它使用整数的按位表示。从每个数组元素的最高有效位开始（暂时忽略其他位）。找到最大的前缀，最大化一/零平衡。现在清除所有数组值，属于前缀并且最高有效位为零（这些值的所有位都为零）。对于后缀中具有非零最高有效位的所有数组值，将所有其他位设置为“一”。将此算法递归地应用于前缀和后缀，使用下一位作为“最重要的”。
这会将原始数组拆分为段。您可以找到每个段的中值并用该中值填充输出数组。或者，在处理前缀时只需在输出数组中设置相应的位，而在处理后缀时将它们保留为零。
所有这些都有效，因为最小化绝对值之和需要找到子数组的中位数，并且在找到这个中位数时，您可以非常近似地比较值，始终只对整个数组使用一个最重要的位并下降到其他位之后，对于子数组。
这是 C++11 代码片段，其中解释了详细信息：
//g++ -std=c++0x
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
typedef vector<unsigned> arr_t;
typedef arr_t::iterator arr_it;
void nonincreasing(arr_it array, arr_it arrayEnd, arr_it out, int bits)
{
if (bits != -1)
{
int balance = 0;
int largestBalance = -1;
arr_it prefixEnd = array;
for (arr_it i = array; i != arrayEnd; ++i)
{
int d = ((*i >> bits) & 1)? 1: -1;
balance += d;
if (balance > largestBalance)
{
balance = largestBalance;
prefixEnd = i + 1;
}
}
for (arr_it i = array; i != prefixEnd; ++i)
{
*(out + (i - array)) += (1 << bits);
if (!((*i >> bits) & 1))
{
*i = 0;
}
}
nonincreasing(array, prefixEnd, out, bits - 1);
for (arr_it i = prefixEnd; i != arrayEnd; ++i)
{
if ((*i >> bits) & 1)
{
*i = (1 << bits) - 1;
}
}
nonincreasing(prefixEnd, arrayEnd, out + (prefixEnd - array), bits - 1);
}
}
void printArray(const arr_t& array)
{
for (auto val: array)
cout << setw(2) << val << ' ';
cout << endl;
}
int main()
{
arr_t array({12,10,10,17,6,3,9});
arr_t out(array.size());
printArray(array);
nonincreasing(begin(array), end(array), begin(out), 5);
printArray(out);
return 0;
}
要处理任何整数，而不仅仅是正数，有两种选择：
这是该算法的高级描述。复杂度为 O(N)。
从搜索子数组开始，从 c[] 的开头开始并具有最大可能的平均值。然后用这个平均值填充 a[] 中相同长度的子数组（四舍五入到最接近的整数并取反）。然后从 a[] 和 c[] 中删除这个子数组（换句话说，假设 a[] 和 c[] 的开头向前移动了子数组的长度）并递归地将此算法应用于 a[] 和 c 的其余部分[]。
该算法最有趣的部分是搜索最大子数组。用来自 c[] 的元素的累积总和填充临时数组 b[]：b[0] = c[0], b[1] = b[0] + c[1], ...现在您可以使用以下方法确定 c[] 中任何间隔的平均值(b[i+m] - b[i]) / m：巧合的是，完全相同的公式（其值的最大化）确定了从 b[i] 到曲线的切线，由 b[] 描述。因此，您可以使用任何Convex hull algorithm一次找到该算法所需的所有最大值（以及子数组边界）。凸包算法通常使用二维点，并且具有超线性复杂度。但在这种情况下，点已经在一维排序，所以格雷厄姆扫描或单调链算法在 O(N) 时间内完成任务，这也决定了整个算法的复杂性。
