Python
 Computer >> コンピューター >  >> プログラミング >> Python

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

  • 0からnの範囲のiの場合、実行

    • 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

  • return（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

  1. Pythonプログラムで配列の合計を見つける

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −配列の合計を計算するために必要な配列が与えられます。 合計を取得するために各インデックスで配列と要素全体をトラバースするブルートフォースアプローチについては、以下で説明します。合計を取得するための各インデックスについては、以下で説明します。 例 # sum function def sum_(arr,n):    # using built-in function    return(sum(arr)) # main arr = [11,22,33,44,55,66

  2. 配列の合計を見つけるPythonプログラム

    この記事では、特定の問題ステートメントを解決するための解決策とアプローチについて学習します。 問題の説明 入力として配列が与えられた場合、与えられた配列の合計を計算する必要があります。 ここでは、ブルートフォースアプローチに従うことができます。つまり、リストをトラバースし、各要素を空の合計変数に追加します。最後に、合計の値を表示します。 以下で説明するように、組み込みの合計関数を使用して別のアプローチを実行することもできます。 例 # main arr = [1,2,3,4,5] ans = sum(arr,n) print ('Sum of the array is '