[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−1​A[i]+y+1∑z−1​A[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−1​A[i],S2​=y+1∑z−1​A[i]
S 1 S 1 S 1はインデックスを1≦i=1 N−1\gei>=1 N≧i>=1に移動し、最大部分和を求める.復帰式は以下の通り.
# 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 S
ショートメール猫ソフトの実現(C#)7 bitPDUの復号化
[コケ]製作13-1