Pythonで配列から要素を削除することで取得できる最大ポイントを見つける

N個の要素を持つ配列Aがあるとすると、2つの整数lとrもあります。ここで、1≤ax≤10^5および1≤l≤r≤Nです。要素を取得します。配列からaxと言って削除し、さらにax + 1、ax+2…ax+Rおよびax-1、ax-2…ax-Lに等しいすべての要素をその配列から削除します。これを行うことにより、それは斧ポイントを要します。アレイからすべての要素を削除した後、総コストを最大化する必要があります。

したがって、入力がA =[2,4,3,10,5]、l =1、r =2の場合、出力は18になります。

これを解決するには、次の手順に従います-

• n：=配列のサイズ

• max_val：=0

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

  • max_val：=max_valの最大値、array [i]

• count_list：=サイズの配列（max_val + 1）、0で埋める

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

  • count_list [array [i]]：=count_list [array [i]] + 1

• res：=サイズの配列（max_val + 1）、0で埋める

• res [0]：=0

• 左：=左、右の最小値

• 1からmax_val+1までの範囲のnumの場合、実行

  • k：=最大数-左-1、0

  • res [num]：=res [num-1]の最大値、num * count_list [num] + res [k]

• res [max_val]

  を返します

例

理解を深めるために、次の実装を見てみましょう-

def get_max_cost(array, left, right) :
   n = len(array)
   max_val = 0
   for i in range(n) :
      max_val = max(max_val, array[i])
   count_list = [0] * (max_val + 1)
   for i in range(n) :
      count_list[array[i]] += 1
   res = [0] * (max_val + 1)
   res[0] = 0
   left = min(left, right)
   for num in range(1, max_val + 1) :
      k = max(num - left - 1, 0)
      res[num] = max(res[num - 1], num * count_list[num] + res[k])
   return res[max_val]
array = [2,4,3,10,5]
left = 1
right = 2
print(get_max_cost(array, left, right))

入力

[2,4,3,10,5] , 1, 2

出力

18