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

 

문제 링크 

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

프로그래머스

 

 

문제 접근 

어떤 수열에 펄스 수열을 원소끼리 곱해서 합이 최대가 되는 부분 수열을 찾아야 한다. 이때 펄스 수열은 [1,-1,1,-1], [-1,1,-1,1]과 같이 1과 -1이 번갈아 나오는 수열을 뜻한다. 

 

먼저 합이 최대가 되는 부분 수열의 합을 구하려면 수열의 누적합을 구한 후 차가 가장 큰 경우를 구하면 된다. 그런데 이 문제에서는 펄스 수열을 곱해야하므로 2가지 수열을 모두 고려해야 한다.

 

문제의 예시를 가지고 펄스 수열을 곱한 결과를 보자.

기본 수열 sequence = [2, 3, -6, 1, 3, -1, 2, 4] 

[1, -1, 1, ...]을 곱한 결과 -> arr1 = [2, -3, -6, -1, 3, 1, 2, -4] 
[-1, 1, -1, ...]을 곱한 결과 -> arr2 = [-2, 3, 6, 1, -3, -1, -2, 4]

arr1의 누적 합 -> [2, -1, -7, -8, -5, -4, -2, -6] 
arr2의 누적 합 -> [-2, 1, 7, 8, 5, 4, 2, 6]

 

우선 최대값은 `8 - (-2) = 10`이 나오고,

여기서 알 수 있는 사실은 누적 합 배열의 `최댓값 - 최솟값`이 답이 된다는 것이다. 이 말은 두 가지 경우를 나눌 필요도 없다는 이야기다. 

 

그래서 펄스 수열 중 1로 시작하는 경우만 고려해서 배열 한 개만을 가지고 문제를 해결했다. 

 

전체 코드 

def solution(sequence):
    answer = 0
    
    # 펄스 수열을 곱한 후 누적 합 생성
    for i in range(1,len(sequence)):
        if i%2 == 1:
            sequence[i] = sequence[i-1] - sequence[i]
        else:
            sequence[i] = sequence[i-1] + sequence[i]
    
    for i in range(len(sequence)):
        answer = max(answer, abs(sequence[i]))
    
    answer = max(answer, max(sequence)-min(sequence))
    
    return answer