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

프로그래머스

 

1. 문제

[입력]

정수 수열 sequence

 

[출력]

연속 펄스 부분 수열의 합 중 가장 큰 것을 return

 

2. 풀이

이 문제의 키 포인트는 연속 부분 수열이라는 점입니다.

따라서 최대 부분 수열의 합은

• 자신이 연속 부분 수열의 포함이 되는 경우
• 자신이 연속 부분 수열의 첫 원소인 경우

위 두 가지 경우 중 큰 값임을 알 수 있습니다.

 

이를 코드로 표현하면 👇🏻 아래와 같습니다.

dp = [0] * len(sequence)
dp[0] = sequence[0]
for i in range(1, len(sequence)):
	pos = sequence[i]
    # dp[i-1] + pos : 자신이 부분 수열에 포함되어 있는 경우
    # pos : 자신이 부분 수열의 첫 원소인 경우
    dp[i] = max(dp[i-1]+pos, pos)

그럼 이제 부분 수열을 구하는 방법을 알았으니, 해당 코드에 펄스를 적용해주어야 합니다.

 

부분 수열의 최대 합을 구하는 것이기 때문에 아래 2개의 배열을 만들어둔다면

특정 index에서 1 또는 -1 로 시작하는 연속 펄스 수열을 만들 수 있습니다. 🤗👍🏻

따라서 1로 시작하는 펄수 수열에서의 최대 수열 합과 -1로 시작하는 펄수 수열에서의 최대 수열 합 중 큰 값을

결과값으로 반환해주면 됩니다. 🪴

 

3. 코드

Python

def solution(sequence):
    return max(solve(sequence,1),solve(sequence,-1))

def solve(sequence,pulse):
    dp = [0] * len(sequence)
    dp[0] = sequence[0] * pulse
    for i in range(1, len(sequence)):
        pulse *= -1
        pos = sequence[i] * pulse
        dp[i] = max(dp[i-1]+pos, pos)
    
    return max(dp)