Programers 연속 펄스 부분 수열의 합/ C++

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

프로그래머스

 

아이디어

1로 시작하는 업펄스 수열과 -1로 시작하는 다운펄스 수열이 곱해진 수를 따로 관리하기 위해 2개의 배열을 관리했고, 펄스배열을 곱한수와 이전 수열들의 부분합 + 펄스배열을 곱한 수를 비교하여 최댓값을 찾는 점화식을 이용했다. 

Prefix Sum과 DP를 적절하게 이용하여 풀이하려했다.

 

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> sequence) {
	auto max = [](long long a, long long b)->long long {return a > b ? a : b; };
	auto max3 = [](long long a, long long b, long long c)->long long { long long temp = a > b ? a : b; return temp>c?temp:c; };
	vector<long long> upPulse(sequence.size(), 0);
	vector<long long> downPulse(sequence.size(), 0);

	downPulse[0] = -sequence[0];
	upPulse[0] = sequence[0];

	long long answer = max(downPulse[0],upPulse[0]);
    
	for (long long i = 1; i < sequence.size(); i++) {
		if (i & 1) {
			downPulse[i] = max(downPulse[i - 1] + sequence[i], sequence[i]);
			upPulse[i] = max(upPulse[i - 1] - sequence[i], -sequence[i]);
		}
		else {			
			downPulse[i] = max(downPulse[i - 1] - sequence[i], -sequence[i]);
			upPulse[i] = max(upPulse[i - 1] + sequence[i], sequence[i]);
		}
		answer = max3(upPulse[i], downPulse[i], answer);
	}
	return answer;
}