Python 中的数组分区 I
我们给定一个数组，假设 arr[] 包含 2n 个整数。我们必须将整数元素的对组组合为 (a1,b1)、(a2,b2)....(an,bn)，使数组中所有元素的 min(ai,bi) 之和尽可能大。任务是找到对的最大和例如 arr[] = [1, 2, 3, 4] 并且输出为 4，则对的最大和为 4。所有可能的是 −
(1, 2) 和 (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4。
(1, 4) 和 (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3。
(1, 3) 和 (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3。
可能的最大和为−4。
Python 中的数组是一个容器，可以存储单一类型的多个值，可以使用对存储在数组中的索引值的引用来访问这些值。需要注意的是，python 不提供数组的内置功能，而是提供 List 的实现。在数组中，索引从 0 开始。例如，arr[0] 是第一个元素，arr[1] 是第二个元素，依此类推，直到 n -1，arr[n-1] 是最后一个元素。数组将元素存储在连续的内存分配中，arr[] 中的 arr 是一个指针，它存储第一个元素的内存。访问数组的所有元素很容易。
在本教程中。在第一种方法中，我们将对数组进行排序，然后通过 for 循环以 2 为增量遍历数组，然后将数组元素添加到 res，然后返回 res。在第二种方法中，对数组进行排序并声明列表 res，然后在 for 循环中以 2 为增量遍历数组，然后附加 a[i] 和 a[i+1]，然后返回数组 res 中最小值的和。在第三种方法中，对数组进行排序并声明变量 count，然后开始循环，直到 count 达到数组的一半，然后将 a[n] 和 a[n+1] 中的最小值添加到 sum，然后将 count 加 1，最后返回 sum。
示例
输入 − arr[] = { 7, 8, 6, 9
输出 − 最大和为:9
解释 − 我们给出了数组 [7, 8, 6, 9]，其中包含 2n 个整数。我们必须将整数对组合成 (a1,b1)、(a2,b2)....(an,bn)，使数组中所有元素的 min(ai,bi) 和尽可能大。任务是找到对的最大和。在这种方法中，我们将对数组进行排序并用 0 初始化数组，然后通过 FOR 循环以 2 为增量遍历数组，然后将 a[i] 添加到变量 res，最后返回 res。最大和为:9。
输入 − arr[] = { 4,9,4,5,9,7
输出 − 最大子数组和为:18
解释 − 我们给出数组 [ 4,9,4,5,9,7]，其中包含 2n 个整数。我们必须将整数对组合成 (a1,b1)、(a2,b2)....(an,bn)，使数组中所有元素的 min(ai,bi) 和尽可能大。任务是找到对的最大和。在这种方法中，我们将对数组进行排序，然后初始化列表 res，然后通过 FOR 循环遍历数组，然后附加 arr[i] 和 arr[i+1] 并返回 res 数组中最小值的和。
以下程序中使用的方法如下
第一种方法
输入数组元素
打印数组。
然后通过将数组作为参数传递来调用 arrayPairSum() 以打印最大和。
在 arrayPairSum() 内部。
用 0 初始化变量 res。
对数组进行排序。
然后以 2 为增量从 0 开始循环 FOR 直到小于 len(a)-1。
然后将 a[i] 添加到 res。
然后返回 res。
第二种方法
输入数组元素。
打印数组。
然后通过将数组作为参数传递来调用 arrayPairSum() 以打印最大和。
在 arrayPairSum() 内部。
对数组进行排序。
初始化列表 res。
从 0 开始循环 FOR 直到小于 len(a)，增量为 2。
将 a[i] 和 a[i+1] 对附加到 res。
然后从 res 返回 min(r) 的总和列表。
第三种方法
输入数组元素。
打印数组。
然后通过将数组作为参数传递来调用 arrayPairSum() 以打印最大和。
在 arrayPairSum() 内部。
对数组进行排序。
然后用 len(a) 初始化变量 l。
用 0 初始化变量 sum、n 和 count。
然后启动循环 WHILE count
然后添加 a[n] 和 a[n+1] 的最小值。
然后将 n 增加 2。
然后将计数增加 1。
最后返回总和。
示例 1
class Solution(object): def arrayPairSum(self, a): res = 0 a = sorted(a) for i in range(0,len(a)-1,2): res += a[i] return res ob1 = Solution() arr = [90,23,76,21,38] print("The array is:",arr) print("The maximum sum is:",ob1.arrayPairSum(arr))
输出
如果我们运行上述代码，它将生成以下输出 -
The array is: 90,23,76,21,38 The maximum sum is: 59
示例 2
class Solution(object): def arrayPairSum(self, a): a = sorted(a) res = [] for i in range(0, len(a), 2): res.append((a[i], a[i+1])) return sum([min(r) for r in res]) ob1 = Solution() arr = [17,18,16,19] print("The array is:",arr) print("The maximum sum is:",ob1.arrayPairSum(arr))
输出
如果我们运行上述代码，它将生成以下输出 -
The array is: 17,18,16,19 The maximum sum is: 34
示例 3
class Solution(object): def arrayPairSum(self, a): a = sorted(a) l = len(a) sum = 0 n = 0 count = 0 while count < l/2: sum += min(a[n], a[n + 1]) n += 2 count += 1 return sum ob1 = Solution() arr = [41,93,43,56,79,87] print("The array is:",arr) print("The maximum sum is:",ob1.arrayPairSum(arr))
输出
如果我们运行上述代码，它将生成以下输出 -
The array is: 41 93 43 56 79 87 The maximum sum is: 184
