# C#LeetCode刷题之#561-数组拆分 I（Array Partition I）

n 是正整数,范围在 [1, 10000].

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Input: [1,4,3,2]

Output: 4

Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

```public class Program {

public static void Main(string[] args) {
int[] nums = null;

nums = new int[] { 1, 4, 3, 2 };
var res = ArrayPairSum(nums);
Console.WriteLine(res);

}

private static int ArrayPairSum(int[] nums) {
Array.Sort(nums);
var sum = 0;
for(int i = 0; i < nums.Length; i += 2) {
sum += nums[i];
}
return sum;
}

}```

`4`

LeetCode 并没有把这题打上贪心标签，我觉得是可以讨论的。我们要解的是所有子数组 min 之后的最大和，这是一种典型的需要贪心思想求解的题目，以局部最优解合并得出整体最优解，所以关键点在于贪心策略的选择。那么对于该题来说贪心策略显然为每个子数组中的2个数的差的绝对值在最小时，整个数组合并出的 min 值最大；否则，若2个数的差的绝对值过大，那么对于整个拆分过后的数组来说，损失了过多的值。也就是说，我们直接排序之后，取出奇（）数值相加即可。

(1)