연속 펄스 부분 수열의 합

문제

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

프로그래머스

솔루션

• 펄스 수열은 [1,-1,1,-1] 또는 [-1,1,-1,1] 임.
• 특정 배열에 위의 펄스 수열 2가지를 각각의 원소에 곱해주면 둘은 부호만 반대 될 뿐 절대값은 같음
• 따라서 원래의 배열에 [1,-1,1,-1] 과 [-1,1,-1,1] 을 각각 곱한 뒤 두가지 배열을 추출하는 것이 아닌 [1,-1,1,-1]을 곱한 뒤 그것의 최댓값과 최솟값을 구한다. 최댓값과 최솟값은 [-1,1,-1,1]을 곱했을 때의 최솟값과 최댓값이므로 [1,-1,1,-1]을 곱한 뒤 나온 최댓값과 최솟값에 절대값을 구한 뒤 둘 중 더 큰 값이 정답이 됨. 
• 그런데 부분 수열의 합을 구하기 위해 이중 반복문을 돌릴 경우 O(n^2)이 되므로 최대 길이가 500_000일 경우에는 시간 초과가 뜸.
• dp를 활용해서 합을 도출 (col 0은  최솟값, 1은 최댓값으로 생각) 
• dp[i][0]은 i번째 원소를 마지막으로 포함할 때의 모든 연속 부분 수열중 최솟값 [i][1]은 최댒값
• dp[i][0] = min ( arr[i], arr[i]+dp[i-1][0] ) 
• dp[i][1] = max ( arr[i], arr[i]+dp[i-1][1] )

코드

from copy import deepcopy


def solution(sequence):
    answer = 0
    n = len(sequence)
    k = 1
    for i in range(n):
        sequence[i] *= k
        k *= -1
    dp = [[0, 0] for i in range(n)]
    dp[0] = [sequence[0], sequence[0]]

    min_val = 100_000_000
    max_val = -100_000_000
    for i in range(1, n):
        dp[i][0] = min(sequence[i], sequence[i]+dp[i-1][0])
        dp[i][1] = max(sequence[i], sequence[i]+dp[i-1][1])

    min_val = min(map(min, dp))
    max_val = max(map(max, dp))

    return max(abs(min_val), abs(max_val))


print(solution([2, 3, -6, 1, 3, -1, 2, 4]))