algorithm - 基于动态编程的之字形拼图

我发现了这个有趣的动态编程问题，需要重新排序整数序列以最大化输出。
史蒂夫有几瓶酒。N瓶的酒精量由ith给出。现在他想从每个酒瓶里喝一杯，这样酒的总宿醉就最大化了。
总宿醉的计算如下（假设'酒精量'数组使用1为基础的索引）：

int hangover=0 ;
for( int i=2 ; i<=N ; i++ ){
    hangover += i * abs(A[i] - A[i-1]) ;
}

所以，很明显，他喝每瓶酒的顺序会改变宿醉的总量。他可以按任何顺序喝这些酒，但每瓶只能喝一杯。而且，一旦他开始喝一杯酒，他会先喝完，然后再去喝别的酒。
史提夫对他应该喝酒的顺序感到困惑，从而使宿醉最大化。帮助他找到他能承受的最大的宿醉，如果他可以喝任何酒类。
输入格式：
第一行包含测试用例数A[i]。每个测试用例的第一行包含T，表示水果的数量。下一行包含N分隔的整数，表示每个水果的甜度。

2
7
83 133 410 637 665 744 986
4
1 5 9 11

我尽我所能，但我没能得到一个o（n^2）的解决方案。通过简单地计算所有排列的宿醉总量，得到了一个o（n！）时间复杂度。这个问题能更有效地解决吗？
谢谢！

最佳答案

我的直觉是：用一种“贪婪链接算法”代替dp。
1）找出差异最大的一对（o（n^2））
2）从其中一个开始，依次找到下一个差异最大的元素，形成一种“链”（2x o（n^2））
3）一旦你为两个人都做了，你就有两个“总数”返回最大的一个作为您的最佳答案。
这种贪婪的策略应该有效，因为问题本身的本质就是贪婪的：为最后一瓶酒选择最大的差异，因为这瓶酒的指数最大，所以结果总是大于一些“妥协”的选择（一种将较小但大致一致的差异分配给指数的选择）。
复杂性：O（3n ^ 2）。可以探测到。如果使用链表而不是静态数组+布尔标志数组，则将其减少为O（3/2 n^2）。
伪ish码：

int hang_recurse(int* A, int N, int I, int K, bool* F)
{
    int sum = 0;
    for (int j = 2; j <= N; j++, I--)
    {
        int maxdiff = 0, maxidx;
        for (int i = 1; i <= N; i++)
        {
            if (F[i] == false)
            {
                int diff = abs(F[K] - F[i]);
                if (diff > maxdiff)
                {
                    maxdiff = diff;
                    maxidx = i;
                }
            }
        }
        K = maxidx;
        F[K] = true;
        sum += maxdiff * I;
    }
    return sum;
}

int hangover(int* A, int N)
{
    bool* F = new bool[N];
    int maxdiff = 0;
    int maxidx_i, maxidx_j;
    for (int j = 2; j <= N; j++, I--)
    {
        for (int i = 1; i <= N; i++)
        {
            int diff = abs(F[j] - F[i]);
            if (diff > maxdiff)
            {
                maxdiff = diff;
                maxidx_i = i;
                maxidx_j = j;
            }
        }
    }
    F[maxidx_i] = F[maxidx_j] = true;
    int maxsum = max(hang_recurse(A, N, N - 1, maxidx_i, F),
                     hang_recurse(A, N, N - 1, maxidx_j, F));
    delete [] F;
    return maxdiff * N + maxsum;
}