欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法

程序员文章站 2022-07-16 08:02:46
...

这个题目的要求是给定一个数组,有2N个元素,将其划分为N对(每一对有两个元素),使得每一对中的最小的元素相加的总和最大,例如:

有一个数组:
s=a1+b1+a2+b2+a3+b(3)+…+an+bn;

我们的目标是将数组划分诸如:
(a1,b1),(a2,b2),(a3,b3),….(an,bn)
然后求:
Sm = min(a1, b1) + min(a2, b2) + … + min(an, bn)
假设对于每一组bi>=ai,Sm(Sm = a1 + a2 + … + an)的最大值就是我们的目标.

定义
1、Sa = a1 + b1 + a2 + b2 + … + an + bn,对于输入的数组来说Sa是一个常数;
2、di = |ai - bi|,Sd = d1 + d2 + … + dn
所以我们可以得到Sa=a1 + a1 + d1 + a2 + a2 + d2 + … + an + an + di = 2Sm + Sd => Sm = (Sa - Sd) / 2

因为Sa是一个常量,要使得Sm最大的话,我们就要使得Sd最小。
一个数组中如何求的Sd最小呢,假如这个数组是一个已排序的数组:
(a1<=b1<=a2<=b2,那么Sd=(b1-a1)+(b2-a2),下图形象地说明了这点:
算法<Array Partition I>
代码实现:

  public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = 0; i < nums.length; i += 2) {
            result += nums[i];
        }
        return result;
    }