Lesson3のTapeEquilibriumは右と左のブロック和の差の絶対値の差を考えるという問題です。
文章だけだと何のことって感じですよね笑
具体的にみていきます。
例えば長さ4の配列[3,1,2,4,3]について二つのブロックに分割することを考えます。
まず2番目で右と左の二つのブロックに分割したらどうなるでしょうか。
右の和 = 3 + 1 = 4
左の和 = 2 + 4 + 3 = 9
よって右と左のブロックの差の値は4-9 = -5であり、その絶対値は5です。
1番目で右と左の二つのブロックに分割したらどうなるでしょうか。
右の和 = 3
左の和 = 1 + 2 + 4 + 3 = 10
よって右と左のブロックの差の値は3-10 = -7であり、その絶対値は7です。
このようにして1番目、2番目、３番目…と配列に対して、次々と右と左のブロック和の差の絶対値を考え、その最小値を求めていきます。
今回ですと３番目で分割した時、
右の和 = 6
左の和 = 7
右と左のブロック和の差 = -1、絶対値の値1が最小となります。
このように、任意の配列に対して、差の絶対値の最小値を求めていきます。
アルゴリズムは以下の通りです。
1.最初に右と左の差の絶対値の最小値の初期設定をしておいく。
2.右と左の値を更新し、新た差の絶対値の値を求めていく。先の差の絶対値の最小値と比較して、新しい方が小さければ、新たな差の絶対値の最小値として更新していく。
3.2を繰り返し行い、配列の差の絶対値の最小値を求めていく。
コードは以下の通りです。
def solution(A):
len_A = len(A)
p = 1
sum_left = A[0]
sum_right = sum(A) - A[0]
sum_difference = abs(sum_left - sum_right)
sum_difference_min = abs(sum_left - sum_right)
while p < len_A:
p += 1
sum_left = sum_left + A[p-1]
sum_right = sum_right - A[p-1]
sum_difference = abs(sum_left - sum_right)
if sum_difference <= sum_difference_min:
sum_difference_min = sum_difference
return sum_difference_min
さて結果は。。。。？
あれ、84%？？？
考え方でどこが間違っているか、わかる方いたら教えてください。