使陣列中的元素之間的差異最大化

-1

將整數的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的總和嗎？

來源

2013-06-30 OneMoreError

有時候，孩子應該承載更多的重量，最大限度差異。

例如，如果權重是[1,2,3,4]，k是3，kid應該取[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])) 
    )

來源

2013-06-30 06:42:39 falsetru

你缺少的測試用例是k可能大於n-k。

所以要k作爲分（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

返回值是您所需答案

來源

2013-06-30 06:10:38 banarun

爲什麼在python中有切片時爲'in範圍（K）？ – mishik

@mishik對不起我不擅長python。我剛剛發現他的錯誤 – banarun

使用這個：'爲我在範圍（K）' - >'爲一個在ARR [：K]：r + = a' '爲我在範圍（nk）' - >'爲a arr [K：]：s + = a' – mishik

使陣列中的元素之間的差異最大化

回答

相關問題