문제
- 연속 펄스 부분 수열의 합 중 가장 큰 것 구하기
- 펄스 수열 : 1 또는 -1 이 번갈아 나오는 수열
- 연속 펄스 부분 수열 : 수열의 연속 부분 수열에 같은 길이의 펄스 수열의 각 원소 곱한 수열
- 1 <= (수열 길이) <= 500,000
- -100,000 <= (수열의 원소) <= 100,000
풀이 1
- 각 연속 부분 수열에 곱할 수 있는 펄스 수열은 2개 (1로 시작할 때, -1로 시작할 때)
- 연속 부분 수열에서 (홀수 번째 합 - 짝수 번째 합) 과 (짝수 번째 합 - 홀수 번째 합) 2개가 된다.
- 홀수 번째의 누적합과 짝수 번째의 누적합을 구해두고, 모든 경우의 수 확인하기
- 시간 복잡도 : $O(N^2)$
- 통과되지 않을 거라는걸 알고 있었지만 역시나 시간초과
- 전체 수열에서 연속 부분 수열은 길이 1 ~ N까지, 각 시작점에서 존재
- N + (N-1) + ... + 1 => $N^2$ 개 이상의 경우의 수가 존재한다.
import sys
def solution(sequence):
n = len(sequence) # sequence 길이
odd_sum = [0] # 홀수 누적합
for i in range(0, n, 2):
odd_sum.append(odd_sum[-1]+sequence[i])
odd_sum.append(odd_sum[-1])
eve_sum = [0, 0] # 짝수 누적합
for i in range(1, n, 2):
eve_sum.append(eve_sum[-1]+sequence[i])
eve_sum.append(eve_sum[-1])
answer = -sys.maxsize
for s in range(1, n+1):
# sequence[s:s+l] : (s+l-1)까지 합 - (s-1)까지의 합
for l in range(1, n-s+2):
odd = odd_sum[s+l-1] - odd_sum[s-1]
eve = eve_sum[s+l-1] - eve_sum[s-1]
answer = max(answer, odd-eve, eve-odd)
return answer
풀이 2
- "시간을 줄여야한다" 로 생각이 든건 DP
- dp[n][2][2] : n번째까지 수열 중 / n번째를 포함할 때 안할 때 / 부호가 + -
- dp[n][0][0] : n번째까지 n번째를 포함하지 않을 때, 짝수 부호가 +
- dp[n][0][1] : n번째까지 n번째를 포함하지 않을 때, 짝수 부호가 -
- dp[n][1][0] : n번째까지 n번째를 포함할 때, 짝수 부호가 +
- dp[n][1][0] : n번째까지 n번째를 포함할 때, 짝수 부호가 -
- 시간 복잡도 : O(N)
import sys
def solution(sequence):
n = len(sequence) # sequence 길이
# dp 테이블
dp = [[[-sys.maxsize]*2 for _ in range(2)] for _ in range(n)]
# dp 테이블 초기화 - 자기 자신일 때를 최댓값으로 설정
for i in range(n):
flag = 1 if i % 2 else -1 # flag : 홀수면 1 짝수면 -1
dp[i][1][0] = sequence[i] * (-flag) # 짝수 부호가 +
dp[i][1][1] = sequence[i] * flag # 홀수 부호가 +
for i in range(1, n):
# i 번째를 포함하지 않을 때 최댓값
dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][1][0])
dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][1])
# i 번째를 포함할 때 최댓값
flag = 1 if i % 2 else -1 # flag : 홀수면 1 짝수면 -1
dp[i][1][0] = max(dp[i][1][0], dp[i-1][1][0] + sequence[i] * (-flag))
dp[i][1][1] = max(dp[i][1][1], dp[i-1][1][1] + sequence[i] * flag)
return max(dp[n-1][0][0], dp[n-1][0][1], dp[n-1][1][0], dp[n-1][1][1])
풀이 3
- 더 간단한 DP 점화식
- dp[0][n] : n번째까지 중 현재 부호가 + 일 때, 최댓값
- dp[1][n] : n번째까지 중 현재 부호가 - 일 때, 최댓값
- 새로운 구간합을 시작하는 경우 vs (이전까지 구간합 + 현재 값) 을 비교한다.
def solution(sequence):
N = len(sequence)
# dp 테이블
dp = [[0] * N for _ in range(2)]
# dp 테이블 초기화
dp[0][0] = sequence[0] # 짝수일 때 +
dp[1][0] = sequence[0] * -1 # 짝수일 때 -
for i in range(1, N):
# i번째로 새로운 구간 시작 vs (이전까지 구간합 + 현재 값)
dp[0][i] = max(sequence[i], dp[1][i-1] + sequence[i])
dp[1][i] = max(-sequence[i], dp[0][i-1] - sequence[i])
return max(max(dp[0]), max(dp[1]))
풀이 4
- 펄스 적용된 sequence에서 구간[a-b]의 합이 최대가 정답
- 최대 누적합[b] - 최소 누적합[a] 인 구간[a,b]가 최댓값을 갖는 연속 부분 수열이 된다.
def solution(sequence):
answer = 0
prefixS = [0]
for i in range(len(sequence)):
# [1, -1, .., ] 펄스 적용
pulse = 1 if i % 2 == 0 else -1
# 구간합 구하기
prefixS.append(prefixS[-1] + pulse * sequence[i])
# 최대 누적합[b] - 최소 누적합[a] 인 구간[a,b]가 최댓값을 갖는 연속 부분 수열
return abs(max(prefixS) - min(prefixS))
References
- 프로그래머스 Lv3 연속 펄스 부분 수열의 합
