Максимальное различие между элементами в массиве

Question

Массив целых чисел N делится на две части: K и N-K элементы, так что необходимо разделить разницу между суммой элементов в этих двух частях.

TEST CASES 
N=5, K=2 
arr = [8 4 5 2 10] 
O/P: 17 because (8+5+10) − (4+2) = 23 − 6 = 17. 

N=8, K=3 
arr= [1 1 1 1 1 1 1 1] 
O/P: 2 because (1+1+1+1+1)-(1+1+1)=2 

То, что я пытаюсь сделать, это сначала суммировать все элементы массива. Затем найдите сумму наименьших K элементов в массиве и вычтите два раза из последнего из первого.

def smallestKSum(arr,K): 
    # returns the sum of the smallest K now. in the array 
    arr.sort() 
    r=0 
    for i in range(K): 
     r=r+arr[i] 
    return r 

N,K = map(int,raw_input().split()) 
arr = map(int,raw_input().split()) 
s = sum(arr) 
print s-(2*smallestKSum(arr,K)) 

выше решение прекрасно работает на вышеуказанных тестовых случаях, но все же это говорит Wrong Solution, когда я пытаюсь представить его. Вы можете проверить проблему на этом link.

Есть ли что-то, что мне не хватает? И могу ли я найти сумму наименьших K nos без сортировки массива?

Answer 1

Иногда, ребенок должен иметь больший вес, чтобы максимизировать разницу.

Например, если веса [1,2,3,4], k равно 3, ребенок должен принимать [2,3,4].

(2 + 3 + 4) - (1) = 8

нет, [1,2,3]

(1 + 2 + 3) - (4) = 1

def smallestKSum(xs, k): 
    xs = sorted(xs) 
    return max(
     abs(sum(xs[k:]) - sum(xs[:k])), 
     abs(sum(xs[-k:]) - sum(xs[:-k])) 
    ) 

Answer 2

Неверный тестовый пример, k может быть больше n-k.

так что К, как мин (п-к, к)

Почему вы не найти сумму остальных элементов в одной и той же функции вместо суммирования всех и снова вычитанием. Попробуйте это:

def smallestKSum(arr,K): 
    # returns the sum of the smallest K now. in the array 
    arr.sort() 
    r=0 
    s=0 
    for a in arr[:K]: 
     r += a 
    for a in arr[K:]: 
     s += a 
    return s-m 

Возвращаемое значение Ваш ответ требуется