問題
今回はMaximum sum of 'i*arr[i]' among all rotations of a given arrayの問題。与えられたリストをローテーションしながら、リストの要素のインデックスをかけ合わせて、最大値を見つけるという問題。
Input: arr[] = {8, 3, 1, 2}
Output: 29
つまり、8, 3, 1, 2というリストであれば、リストをローテーションさせると、下記のよう4個のパターンがあるので、このパターンでインデックスをかけ合わせたときに、最大値がいくらになるかを調べる問題。
{8, 3, 1, 2} = 8*0 + 3*1 + 1*2 + 2*3 = 11
{3, 1, 2, 8} = 3*0 + 1*1 + 2*2 + 8*3 = 29 * answer
{1, 2, 8, 3} = 1*0 + 2*1 + 8*2 + 3*3 = 27
{2, 8, 3, 1} = 2*0 + 8*1 + 3*2 + 1*3 = 17
実装
問題を分解するために、ループごとにリストをローテーションさせて、インデックスをかけて、値を比較してという作業を繰り返すという方法を考えたが、そうではなく、リストから値を引き出すインデックスをうまく作れば、リスト自体をローテーションするという無駄な作業が発生しないとのこと…なるほど、賢い。
このイメージを可視化したものが下記の画像。iのインデックスは組み合わせを管理し、jのインデックスをかけ合わせるが、int((i + j) % len_numbers)でiのインデックスの値が足し込まれることで、うまく1つずつずれて、インデックスが循環する。循環みたいなものを表現するのに、剰余は強力だと再認識しました。
int((i + j) % len_numbers)の部分を可視化するとこのようになります。
def maxSum(numbers):
len_numbers = len(numbers)
print('-'*30)
for i in range(len_numbers):
curr_sum = 0
for j in range(len_numbers):
index = int((i + j) % len_numbers)
if j != len_numbers-1:
curr_sum += j * numbers[index]
print('{}*{} +'.format(numbers[index], j), end=' ')
else:
curr_sum += j * numbers[index]
print('{}*{} = {}'.format(numbers[index], j, curr_sum), end=' ')
print()
print('-'*30)
numbers = [8, 3, 1, 2]
maxSum(numbers)
------------------------------
8*0 + 3*1 + 1*2 + 2*3 = 11
------------------------------
3*0 + 1*1 + 2*2 + 8*3 = 29
------------------------------
1*0 + 2*1 + 8*2 + 3*3 = 27
------------------------------
2*0 + 8*1 + 3*2 + 1*3 = 17
------------------------------
ということで、不要な部分を削除して書き直したものがこちら。
def maxSum(numbers):
len_numbers = len(numbers)
res = 0
for i in range(len_numbers):
curr_sum = 0
for j in range(len_numbers):
index = int((i + j) % len_numbers)
curr_sum += j * numbers[index]
res = max(res, curr_sum)
return res
numbers = [8, 3, 1, 2]
print(maxSum(numbers))
29
