通过重新排列数组来最大化数组的绝对差之和 [英] maximize summation of absolute difference of array by rearranging the array

问题描述

以summation of the absolute differences between every two adjacent numbers is maximum

array =(1，2，7) 安排是(1,7,2)

array=( 1, 2, 7) arrangement is (1,7,2)

sum=|1-7|+|7-2|=11

推荐答案

您可以在O(nlogn)中进行操作.请仔细考虑...

You can do so in O(nlogn).Think before...

1. 排序数组1 2 3 4 5

2. 选择left = 5 right = 5，这是最大值.我是1，而j是4，因此我给出了最大绝对差，所以

1. Sort the array 1 2 3 4 5

2. Select left=5 right=5 that is the maximum. i is 1 and j is 4 and i gives max absolute difference so

根据最大绝对差在其右侧或左侧添加.在此处以i表示右侧

Append on its right or left based upon max absolute difference.Here its on right with i

现在left = 1和right = 2和4与左差最大

Now left=1 and right=2 and 4 gives max difference with left so

最后，左和右的差异为3

Finally its same difference for left and right with 3

代码:-( C ++)

CODE:-(C++)

sort(a.begin(),a.end());
int l=a[a.size()-1]; //left
int r=l;             // right
int i=0,j=a.size()-2;
long long int sum=0;
while(i<j){
        int li=abs(l-a[i]),ri=abs(r-a[i]);
        int lj=abs(l-a[j]),rj=abs(r-a[j]);
        if(li>ri||lj>rj){ //left side
                if(li>lj){
                        sum+=li;
                        l=a[i++];
                }else{
                        sum+=lj;
                        l=a[j--];
                }
        }else{
                if(ri>rj){
                        sum+=ri;
                        r=a[i++];
                }else{
                        sum+=rj;
                        r=a[j--];
                }
        }
        //cout<<l<<"---"<<r<<"------"<<i<<"---"<<j<<"----------"<<sum<<endl;
}
sum+=MAX(abs(l-a[i]),abs(r-a[i]));
cout<<sum<<endl;

这篇关于通过重新排列数组来最大化数组的绝对差之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！