1
4
1 2 3 4

6

求删除每个数后的序列最大差值的和

记录第一 第二 第三大的和，每次删除点时删除掉两个差值，新加入一个差值  第一个的最后一个数只删除一个差值

/************************************************
┆  ┏┓　　　┏┓ ┆
┆┏┛┻━━━┛┻┓ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　━　　　┃ ┆
┆┃　┳┛　┗┳　┃ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　┻　　　┃ ┆
┆┗━┓　  　┏━┛ ┆
┆　　┃　  　┃　　┆　　　　　　
┆　　┃　  　┗━━━┓ ┆
┆　　┃　 AC代马 　　┣┓┆
┆　　┃　        　　┏┛┆
┆　　┗┓┓┏━┳┓┏┛ ┆
┆　　　┃┫┫　┃┫┫ ┆
┆　　　┗┻┛　┗┻┛ ┆
************************************************ */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#define ll long long
using namespace std;

int a[100010],Max[100010];

int Abs(int i)
{
    return i>0?i:(-i);
}

bool cmp(int i,int j)
{
    return i>j;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(Max,-1,sizeof(Max));
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(int i=0;i<n-1;i++)
        Max[i]=Abs(a[i]-a[i+1]);
        sort(Max,Max+n-1,cmp);
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            if(i==0)
            {
                int num=Abs(a[1]-a[0]);
                if(num==Max[0])
                {
                    ans+=Max[1];
                }
                else ans+=Max[0];
            }
            else if(i==n-1)
            {
                int num=Abs(a[n-1]-a[n-2]);
                if(num==Max[0])
                {
                    ans+=Max[1];
                }
                else ans+=Max[0];
            }
            else
            {
                int num1=Abs(a[i]-a[i-1]);
                int num2=Abs(a[i]-a[i+1]);
                int num3=Abs(a[i+1]-a[i-1]);
                if(num1==Max[0]&&num2==Max[1])
                {
                    ans+=max(num3,Max[2]);
                }
                else if(num1==Max[1]&&num2==Max[0])
                {
                    ans+=max(num3,Max[2]);
                }
                else if(num1==Max[0])
                {
                    ans+=max(num3,Max[1]);
                }
                else if(num2==Max[0])
                {
                    ans+=max(num3,Max[1]);
                }
                else ans+=max(num3,Max[0]);
            }
        }
        printf("%lld\n",ans);
    }
}

hdu NanoApe Loves Sequence

原文：http://blog.csdn.net/u013097262/article/details/52138246