[ 프로그래머스 / LV3 ] 연속 펄스 부분 수열의 합 ( Python 파이썬 )

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

프로그래머스

 

코드

---

def solution(sequence):
    table = [[0 for _ in range(len(sequence) + 1)] for _ in range(2)]
    weight = 1
    for i in range(len(sequence)):
        table[0][i + 1] = table[0][i] + sequence[i] * weight
        table[1][i + 1] = table[1][i] - sequence[i] * weight
        weight *= -1
    return max(max(table[0]) - min(table[0]), max(table[1]) - min(table[1]))

 

풀이

---

누적합을 이용한 풀이이다. 내가 해결한 코드는 아니고 '다른 사람의 풀이'에서 가장 위에 있던 코드를 가져와봤다.

나는 투포인터를 사용해서 이리저리 휘둘리다가 포기해버렸다...

 

sequence를 한 번 탐색(O(n))하며 펄스(1,-1)별로 누적합을 구한다.

이렇게 만들어진 누적합 배열에서 합이 최대인 부분수열을 구하는 방법은 (최대값 - 최소값)이다.

 따라서 두 펄스에서의 누적최대값을 구하면 간단하게 해결이 가능하다.