Given an array with maximum sum, locate two number which produce the maximum sum without exceeding the maximum

Daniel Stafford 0
Viewed 26

I have the following code that counts the number of pairs in an array that have a sum below the maximum,

def findPairs(arr, x):
 
    l = 0; r = len(arr)-1
    result = 0
 
    while (l < r):
     
        if (arr[l] + arr[r] < x):
         
            result += (r - l)
            l += 1
         

        else:
            r -= 1
 
    return result
     
arr = [1, 2, 3, 4, 5, 6, 7, 8]
n = len(arr)
x = 7
print(findPairs(arr, x))

I need to edit it in order to return a list of the pair with the maximum sum not exceeding the maximum parameter (x). If there are multiple pairs with the maximum sum then one pair is chosen at random

arrays python
2 Answers

You can use the itertools.combinations method to get all possible combinations of a list.

from itertools import combinations

def findPair(arr):
    allcomm = combinations(arr,2)
    allcomm = filter(lambda e:sum(e)<=max(arr),allcomm)

    return max(allcomm,key=sum)

        

arr = [1, 2, 3, 4, 5, 6, 7, 8]


print(findPair(arr))

output

(1, 7)
  1. First I use itertools.combination method to the all possible combination of an array.
  2. I use the filter method to get only the pair whose sum is less than the max number in the arr.
  3. Then I use the max function to get the maximum sum pair in the allcomm array.
codester_090

Without additional modules (which would potentially make the implementation more efficient) you could just do this:

def find_pairs(arr, m):
    c = 0
    pair = None
    for i, x in enumerate(arr[:-1]):
        for y in arr[i+1:]:
            if x + y < m:
                c += 1
                pair = x, y
    return c, pair

arr = [1, 2, 3, 4, 5, 6, 7, 8]
m = 7

print(find_pairs(arr, m))

Output:

(6, (2, 4))
Vlad0
Related