[Python/Programmers] 연속 펄스 부분 수열

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

프로그래머스

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

풀이

Code

def solution(sequence):
    # 1. 2차원 구간 합 리스트 생성
    prefix_sum = [[0] * len(sequence) for _ in range(2)]
    # 2.펄스 변수 생성
    temp_0, temp_1 = 1, -1
    # 3. 최솟값 변수 설정
    min_0 = min_1 = 0
    answer = -float('inf')
    # 4. 
    for i in range(len(sequence)) :
        # 4-1. 각 펄스에 맞게 누적합 생성 후 해당 인덱스 값에 저장
        if i == 0 :
            prefix_sum[0][i] = sequence[i] * temp_0
            prefix_sum[1][i] = sequence[i] * temp_1
        else :
            prefix_sum[0][i] = prefix_sum[0][i-1] + sequence[i] * temp_0
            prefix_sum[1][i] = prefix_sum[1][i-1] + sequence[i] * temp_1
        # 4-2. 결과값 업데이트
        answer = max(answer, prefix_sum[0][i] - min_0, prefix_sum[1][i] - min_1) if i > 0 else max(answer, prefix_sum[0][i], prefix_sum[1][i])
        # 4-3. 최솟값 업데이트
        min_0 = min(min_0, prefix_sum[0][i])
        min_1 = min(min_1, prefix_sum[1][i])
        # 4-4. 펄스 변환
        temp_0 *= -1
        temp_1 *= -1
    # 5. 결과 리턴
    return answer