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

 

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

프로그래머스

 

---

 

문제 해결 과정

착안

동적계획법(dynamic programming)을 통해 부분 수열의 합을 구하는 알고리즘을 응용하여 펄스 부분 수열의 합을 구한다.

 

구현

이전 포스트에서 사용한 방법을 동일하게 적용하되, 원래 수열에 곱할 수 있는 펄스 수열은 1 또는 -1로 시작하는 두 가지의 경우가 있으므로, 원래 수열에 1과 -1로 시작하는 각각의 펄스 수열을 길이만큼 곱한 수열에 대해 부분 수열의 합을 구하는 방식으로 문제를 해결하였다.

 

예시) 주어진 수열이 1, 2, 3, 4, 5 인 경우

• 1, -2, 3, -4, 5 에 대한 부분 수열의 합 중 최댓값을 계산
• -1, 2, -3, 4, -5 에 대한 부분 수열의 합 중 최댓값을 계산
• 두 값 중 큰 값을 return

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>

using namespace std;

long long pulsify(vector<int> sequence, int sgn)
{
	long long maxSum = 0;
	long long sum = 0;
	int idx = 0;

	while (idx < (int)sequence.size())
	{
		int num = sgn * sequence[idx];
        
		if (sum + num > 0)
		{
			sum += num;
			if (maxSum < sum)
				maxSum = sum;
		}
		else
			sum = 0;

		sgn *= -1;
		idx++;
	}

	return maxSum;
}

long long solution(vector<int> sequence)
{
	long long num1 = pulsify(sequence, 1);
	long long num2 = pulsify(sequence, -1);

	return num1 > num2 ? num1 : num2;
}

 

실행 결과