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

문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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으로서 가장 큽니다.

---

구현 포인트

pulse

• pulse_a와 pulse_b 두 가지 버전 펄스 전체 배열 생성

DP 배열 (pulse_dp_a, pulse_dp_b)

• 각 배열은 부분 수열의 최대 합을 구하는 데 사용된다.
• pulse_dp_a[i]: pulse_a[i]까지의 부분 수열에서 최댓값을 저장
• pulse_dp_b[i]: pulse_b[i]까지의 부분 수열에서 최댓값을 저장

동적 계획법(DP)

• 이전 값과 현재 값 비교: 각 pulse_dp_a[i]와 pulse_dp_b[i]는 현재 값과 이전 값까지의 누적합을 비교하여 더 큰 값을 저장

풀이

def solution(sequence):
    answer = 0
    
    pulse_a = [sequence[i] * (-1)**(i) for i in range(len(sequence))]
    pulse_b = [sequence[i] * (-1)**(i+1) for i in range(len(sequence))]
    
    # 누적합 배열
    pulse_dp_a = [0 for _ in range(len(sequence))]
    pulse_dp_b = [0 for _ in range(len(sequence))]
    
    pulse_dp_a[0] = pulse_a[0]
    pulse_dp_b[0] = pulse_b[0]
    
    # 이전 값까지 더한 값이 큰지, 현재 값만으로 새로운 부분 수열을 시작하는게 유리한지
    for i in range(1, len(sequence)):
        pulse_dp_a[i] = max(pulse_dp_a[i-1] + pulse_a[i], pulse_a[i])
        pulse_dp_b[i] = max(pulse_dp_b[i-1] + pulse_b[i], pulse_b[i])
    
    answer = max(max(pulse_dp_a), max(pulse_dp_b))

    return answer

• max(pulse_dp_a[i-1] + pulse_a[i], pulse_a[i])
  pulse_dp_a[i-1] + pulse_a[i] : 이전까지의 부분 수열에 현재 값을 추가한 값
  pulse_a[i] : 현재 값을 단독으로 시작 → 이전 값들과는 관계없이, 새로운 부분 수열을 시작하는 경우에 해당