[Codility] 9.1 MaxDoubleSliceSum
5684 ワード
MaxDoubleSliceSum
アレイAについて
triplet(X, Y, Z)=∑x+1y−1A[i]+∑y+1z−1A[i]\textrm{triplet(X, Y, Z)}=\sum_{x+1}^{y-1}A[i]+\sum_{y+1}^{z-1}A[i]triplet(X, Y, Z)=x+1∑y−1A[i]+y+1∑z−1A[i]
2つの部分からなる.したがって,対応する部分協定の最低価格の和を左右することが答えである.ではyyのインデックスを中心に部分和を求めます.S 1、S 2 S 1、S 2 S 1、S 2を定義する.
S1=∑x+1y−1A[i], S2=∑y+1z−1A[i]S_1 =\sum_{x+1}^{y-1}A[i],\;S_2=\sum_{y+1}^{z-1}A[i]S1=x+1∑y−1A[i],S2=y+1∑z−1A[i]
S 1 S 1 S 1はインデックスを1≦i=1 N−1\gei>=1 N≧i>=1に移動し、最大部分和を求める.復帰式は以下の通り.
max()内で0と比較するのは,X,Yが隣接し,Y,Zが隣接すると部分和が0となるためである.
答えのコードは次のとおりです.
アレイAについて
triplet(X, Y, Z)=∑x+1y−1A[i]+∑y+1z−1A[i]\textrm{triplet(X, Y, Z)}=\sum_{x+1}^{y-1}A[i]+\sum_{y+1}^{z-1}A[i]triplet(X, Y, Z)=x+1∑y−1A[i]+y+1∑z−1A[i]
2つの部分からなる.したがって,対応する部分協定の最低価格の和を左右することが答えである.ではyyのインデックスを中心に部分和を求めます.S 1、S 2 S 1、S 2 S 1、S 2を定義する.
S1=∑x+1y−1A[i], S2=∑y+1z−1A[i]S_1 =\sum_{x+1}^{y-1}A[i],\;S_2=\sum_{y+1}^{z-1}A[i]S1=x+1∑y−1A[i],S2=y+1∑z−1A[i]
S 1 S 1 S 1はインデックスを1≦i
# initiate S1, S2
S2[i] = [0, 0, ..., 0]
S2[i] = [0, 0, ..., 0]
# 양끝점은 부분합에 계산하지 않는다. A[X], A[Z]는 제외되기 때문
S1[i] = max(0, S1[i - 1] + A[i]) for i in 1, 2, ..., N-2
S2[i] = max(0, S2[i + 1] + A[i]) for i in N-2, N-1, ..., 1
S[i] = S1[i - 1] + S2[i + 1]max()内で0と比較するのは,X,Yが隣接し,Y,Zが隣接すると部分和が0となるためである.
答えのコードは次のとおりです.
def solution(A):
N = len(A)
if N == 3:
return 0
# initialize S1, S2
S1 = [0] * N
S2 = [0] * N
# Construct S1
for i in range(1, N - 1):
S1[i] = max(0, S1[i-1] + A[i])
# Construct S2
for i in range(N-2, 1, -1):
S2[i] = max(0, S2[i+1] + A[i])
# Calculate S
S = 0
for i in range(1, N-1):
S = max(S, S1[i-1] + S2[i+1])
return SReference
この問題について([Codility] 9.1 MaxDoubleSliceSum), 我々は、より多くの情報をここで見つけました https://velog.io/@ahj1592/Codility-9.1-MaxDoubleSliceSum-Respectableテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol