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

문제

문제 설명

• -1과 1이 번갈아가며 배치된 일정한 크기의 배열을 펄스라고 한다.
• 주어진 배열의 부분 수열과 펄스를 elemental-wise product하여 생성해낸 수열을 펄스 부분 수열이라고 한다.
• 이 때, 펄스 부분 수열의 합 중 최댓값을 구하는 문제

풀이

• -1로 시작하는 펄스와 1로 시작하는 펄스로 누적합 배열 2개를 생성
• 누적합의 최대값과 최소값을 통해서 답을 찾을 수 있다.

def solution(sequence):
    l = len(sequence)
    prefix_sum = [[0] * (l+1) for _ in range(2)]
    for i in range(l):
        if i%2:
            prefix_sum[0][i+1] = prefix_sum[0][i] - sequence[i]
            prefix_sum[1][i+1] = prefix_sum[1][i] + sequence[i]
        else:
            prefix_sum[1][i+1] = prefix_sum[1][i] - sequence[i]
            prefix_sum[0][i+1] = prefix_sum[0][i] + sequence[i]
    return max(max(prefix_sum[0]) - min(prefix_sum[0]), max(prefix_sum[1]) - min(prefix_sum[1]))