[프로그래머스 Lv. 3] 연속 펄스 부분 수열의 합

문제

https://school.programmers.co.kr/learn/courses/30/lessons/161988

접근

동적 계획법으로 접근

1. 2차원 배열로 dp 배열을 생성하고 펄스를 [[1,-1] , [-1,1]] 이런 식으로 정의한다.
2. 그 이 후 이중 포문을 돌리는데 i는 pulse의 인덱스, j는 sequence의 인덱스다.
   2- 1. dp의 처음 값은 sequence[0]으로 정의한다.
   2- 2. 이 후 1부터 sequence의 길이만큼 반복문을 돌린다. 이 때 나머지 연산을 통해 pulse에 순차적으로 접근한다.
3. 포문이 끝난 뒤 가장 큰 값을 반환한다.

Code

def solution(sequence):
    dp =[[0] * (len(sequence) +1) for _ in range(2)]
    pulse =[[1,-1], [-1,1]]
    for i in range(2):
        dp[i][0] = sequence[0] * pulse[i][0]
        for j in range(1, len(sequence)):
            dp[i][j] = max(sequence[j] *pulse[i][j%2] + dp[i][j-1], sequence[j] *pulse[i][j%2])
            
    return (max(max(dp[0]), max(dp[1])))