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

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

프로그래머스

 

 

참 알고리즘 공부하는데 아직도 부족하다고 느껴지는 문제였다.

 

 

이 문제의 알고리즘 분류는 누적합 이다

 

 

기억하자.. 특정구간의 합을 구한다 => 누적합을 쓰자

 

 

 

 

1. 아이디어

 

각 펄스 수열의 누적합을 구한다.

특정 구간의 합이 가장 큰 부분의 합은 누적합의 최소값과 최대값의 차이이다

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

 

 

 

아래는 처음에 푼 멍청한 풀이..

 

for문을 돌리며 sum이 -값이 되면 과감히 버려버리고 다시 sum하며 최대값을 구하는 방식으로 했다.

 

def solution(sequence):
    A = []
    B = []
    C = 1
    for i in sequence:
        A.append(i*C)
        B.append(i*-C)
        C = C*(-1)
    maxA = A[0]
    maxB = B[0]
    sumA = 0
    sumB = 0
    for i in A:
        sumA += i
        if sumA < 0:
            sumA = 0
            continue
        maxA = maxA if maxA > sumA else sumA

    for i in B:
        sumB += i
        if sumB <0:
            sumB = 0
            continue
        maxB = maxB if maxB > sumB else sumB

    answer = maxA if maxA > maxB else maxB
    return answer