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

Об этом предложении

문제 요약 수열의 연속 부분 수열 하나를 선택하고, [1, -1, 1, -1, ...] 또는 [-1, 1, -1, 1, ...] 형태의 펄스 수열을 곱한다. 만들어진 연속 펄스 부분 수열의 합 중 최댓값을 구한다. 핵심 아이디어 펄스 수열의 부호 패턴은 두 가지뿐이다. 패턴 1: 1, -1, 1, -1, ... 패턴 2: -1, 1, -1, 1, ... 원본 수열의 인덱스 기준으로 두 패턴을 미리 곱한 변환 수열을 생각한다. sequence: 2, 3, -6, 1, ... 변환 1: 2, -3, -6, -1, ... 변환 2: -2, 3, 6, 1, ... 어떤 연속 구간을 선택하더라도 두 변환 수열 중 하나의 연속 부분합으로 표현된다. 따라서 두 변환 수열 각각에서 최대 연속 부분합 을 구하고, 둘 중 큰 값을 선택하면 된다. 최대 연속 부분합은 카데인 알고리즘으로 한 번의 순회에 구할 수 있다. 카데인 알고리즘 현재 값이 value 일 때, 현재 위치에서 끝나는 최대 연속 부분합은 두 선택지 중 큰 값이다. current = max(value, current + value) 이전 구간을 버리고 현재 값부터 새로 시작한다. 이전 구간 뒤에 현재 값을 이어 붙인다. 두 변환 패턴의 값을 같은 순회에서 함께 계산할 수 있다. 풀이 과정 짝수 인덱스에서는 첫 번째 패턴의 부호를 1 , 홀수 인덱스에서는 -1 로 둔다. 두 번째 패턴은 첫 번째 패턴의 부호를 반대로 한 값이다. 각 변환 값에 카데인 알고리즘을 적용한다. 두 패턴에서 얻은 최대 부분합 중 큰 값을 반환한다. Python 코드 def solution(sequence): current_first = 0 current_second = 0 answer = -float("inf") for index, value in enumerate(sequence): # 전체 수열 기준 [1, -1, 1, -1, ...] 패턴 first_value = value if index % 2 == 0 else -value second_value = -first_value # 각 패턴에서 현재 인덱스로 끝나는 최대 연속 부분합 current_first = max(first_value, current_first + first_value) current_second = max(second_value, current_second + second_value) answer = max(answer, current_first, current_second) return answer 예시 sequence = [2, 3, -6, 1, 3, -1, 2, 4] 에서 인덱스 1부터 3까지의 구간을 선택해 보자. 원본 구간: [3, -6, 1] 펄스 수열: [1, -1, 1] 곱한 결과: [3, 6, 1] 합: 10 이 구간은 두 번째 변환 패턴에서의 연속 부분합으로 계산되며, 전체 최댓값은 10 이다. 시간 복잡도 N 을 수열 길이라고 하자. 수열을 한 번만 순회하고, 두 개의 현재 부분합만 유지한다. 시간 복잡도: O(N) 공간 복잡도: O(1) 정리 펄스 수열의 시작 부호는 두 가지뿐이다. 두 부호 패턴으로 수열을 변환한 뒤 각각의 최대 연속 부분합을 구하면, 모든 연속 펄스 부분 수열의 합 중 최댓값을 선형 시간에 구할 수 있다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.36

Уверенность

49%