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

문제

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.
펄스 수열이란 [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 함수를 완성해주세요.

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
• sequence의 원소는 정수입니다.

입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

접근

누적합

펄스 수열이 적용된 전체 sequence 배열의 누적합을 이용하여 풀이했다.
다만, 펄스 수열은 2가지(1 또는 -1로 시작)이므로,
각각에 대한 연산을 따로 해주어야 한다.

현재 값 이전에 존재하는 최소값

전체 배열의 누적합을 구하게 되면,
어떤 원소 E를 마지막으로 하는 연속 펄스 부분 수열의 최대합은

E까지의 누적합 $-$ E 이전까지의 누적합의 최소값

으로 구할 수 있다.

따라서, 누적합을 계산함과 동시에 각 원소의 위치(인덱스)까지의 누적합의 최소값을 계산해주고
현재 원소의 누적합과 이전까지의 최소값의 차 중 가장 큰 값을 구해주면 된다.

---

코드

from sys import maxsize

INF = maxsize

def solution(sequence):
    answer = -INF
    size = len(sequence)
    s1 = s2 = 0				# 1
    s1_min = s2_min = 0		# 2
    pulse = 1
    
    for i in range(size):
        s1 += sequence[i] * pulse
        s2 += sequence[i] * (-pulse)
        
        # 3
        answer = max(answer, s1-s1_min, s2-s2_min)
        
        # 4
        s1_min = min(s1_min, s1)
        s2_min = min(s2_min, s2)
        
        # 5
        pulse *= -1
    return answer

1. 각 시퀀스의 누적합

1부터 시작하는 펄스가 적용된 누적합과
-1부터 시작하는 펄스가 적용된 누적합을 각각 구해야 하므로
s1, s2 2개의 변수를 선언했다.

2. 각 시퀀스의 누적합의 최소값

s1_min과 s2_min은 각각 s1, s2의 최소값을 갱신하기 위한 변수이다.

3. 최대값의 갱신

현재까지의 최대값, 두 시퀀스의 누적합과 현재 이전 까지의 누적합 중 최소값의 차 총 3개의 값 중 최대값으로 정답을 갱신해준다.

4. 최소값의 갱신

각 순회시에 최소값의 갱신을 최대값을 갱신한 뒤에 처리했다.
그 이유는 최대값 갱신을 위해 두 누적합의 차를 구할 때,
그 최소값에 현재까지의 누적합이 포함되지 않게 하기 위해서이다.

5. 펄스

매 순회마다 펄스의 부호를 바꿔준다.