最大化数组中元素之间的差异

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个数的和而不排序数组吗？你知道吗

Answer 1

缺少的测试用例是k可能大于n-k

所以把k设为min（n-k，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

返回值是您所需的答案

Answer 2

有时候，孩子应该多负重以最大化差异。你知道吗

例如，如果权重为[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]))
    )