資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢給定陣列所有子集可能的最大差值之和（Python）
假設我們有一個包含 n 個值的陣列 A（元素可能不唯一）。我們必須找到給定陣列所有子集可能的最大差值之和。現在考慮 max(s) 表示任何子集中的最大值，min(s) 表示集合中的最小值。我們必須找到所有可能子集的 max(s)-min(s) 之和。
因此，如果輸入類似於 A = [1, 3, 4]，則輸出將為 9。
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小
對列表 A 進行排序
sum_min := 0, sum_max := 0
對於 i in range 0 到 n，執行：
sum_max := 2 * sum_max + A[n-1-i]
sum_max := sum_max mod N
sum_min := 2 * sum_min + A[i]
sum_min := sum_min mod N
返回 (sum_max - sum_min + N) mod N
示例
讓我們來看下面的實現以更好地理解：
N = 1000000007 def get_max_min_diff(A): n = len(A) A.sort() sum_min = 0 sum_max = 0 for i in range(0,n): sum_max = 2 * sum_max + A[n-1-i] sum_max %= N sum_min = 2 * sum_min + A[i] sum_min %= N return (sum_max - sum_min + N) % N A = [1, 3, 4] print(get_max_min_diff(A))
輸入
[1, 3, 4]
輸出
9
更新於：2020年8月27日
329 次瀏覽
廣告