プログラママップの収集(2)

https://programmers.co.kr/learn/courses/30/lessons/12971
これは,以前の計算結果を用いたdpの問題である.
Nは10万であり,完全探索やdfsなどの手法を用いれば,時間を超える可能性が高い.
従って,dpを用いて従来の区間和を求めることは問題である.
以前の値が選択されているかどうかによって、dp値の選択が変化します.
従ってdpを2つに分け,1番目のdpはdpなしで計算した.

def solution(sticker):
    if len(sticker) == 1:
        return sticker[0]
    dp = [0 for _ in range(len(sticker))] ## 앞의 스티커를 사용했다고 가정
    value = 0
    dp[0] = sticker[0]
    dp[1] = dp[0]
    for i in range(2,len(sticker)-1):
        dp[i] = max(dp[i-2]+sticker[i], dp[i-1])
    value = max(dp)
    
    udp = [0 for _ in range(len(sticker))]
    udp[0] = 0
    udp[1] = sticker[1]
    for i in range(2,len(sticker)):
        udp[i] = max(udp[i-2]+sticker[i], udp[i-1])
    value2 = max(udp)
    
    return max(value,value2)