[Programmers] 연속 펄스 부분 수열의 합

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

비교적 접근하기 쉬웠던 DP 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 펄스 수열은 1로 시작하는 경우와 -1로 시작하는 경우 두 가지입니다.

1.1 따라서 주어진 sequence에 대해 두 가지 펄스 수열을 구하고 이들의 부분 수열 합 중 최대 값을 구하면 됩니다.

2. cache[i]를 i번째 인덱스까지 탐색했을 때 최댓값을 저장하는 dp 배열로 정의했을 때 점화식은 아래와 같습니다.

2.1 v가 펄스 부분 수열이라고 가정했을 때 cache[i] = max(v[i], cache[i -1] + v[i])

2.2 연속성을 보장하기 위해 v[i]는 반드시 포함해야 하기 때문에 i 번째 원소부터 시작하는 부분수열의 합과 기존 부분 수열에 i 번째 원소를 포함할지만 판단하면 됩니다.

2.3 단, 주어진 sequence의 크기가 1일 경우에는 예외처리를 해줘야 합니다.

3. 1.1에서 구한 두 가지 펄스 수열에 대해 2번 과정을 수행한 결과를 반환해 주면 됩니다.

 

 

개발환경: Programmers IDE 

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~