在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，最后返回res中的最小值之和。第三种方法是对数组进行排序，声明变量count，从数组的一半开始循环，将a[n]和a[n+1]的较小值加到sum中，然后将count增加1，最后返回sum。

示例

输入 − arr[] = { 7, 8, 6, 9}

输出 − 最大和为：9

解释

将整数组合成(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”中，并返回“res”数组中的最小值的和。

以下程序使用的方法如下

• 第一种方法
  • 输入数组元素

  • 打印数组。

  • 然后调用arrayPairSum()，将数组作为参数传递以打印出最大和。

  • 在arrayPairSum()内部。

  • 将变量res初始化为0。

  • 对数组进行排序。

  • 然后从0开始循环遍历到len(a)-1，步长为2。

  • 将a[i]添加到res中。

  • 然后返回res。

• 第二种方法

  • 输入数组元素。

  • 打印数组。

  • 然后调用arrayPairSum()，将数组作为参数传递以打印出最大和。

  • 在arrayPairSum()内部。

  • 对数组进行排序。

  • 初始化列表res。

  • 从0开始循环遍历到len(a)-1，步长为2。

  • 将a[i]和a[i+1]的对添加到res中。

  • 然后返回res列表中的min(r)的和。

• 第三种方法

  • 输入数组元素。

  • 打印数组。

  • 然后通过将数组作为参数调用arrayPairSum()来打印最大和。

  • 在arrayPairSum()内部

  • 对数组进行排序。

  • 然后将变量l初始化为len(a)。

  • 将变量sum，n和count初始化为0。

  • 然后开始循环，直到count小于l。

  • 然后将a[n]和a[n+1]中的较小值相加。

  • 然后将n增加2。

  • 然后将count增加1。

  • 最后返回sum。

示例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