[JAVA] DP : 연속 펄스 부분 수열의 합

1. 문제 내용

요약
수열이 있으면 가장 큰 수가 나오는 부분 수열의 합을 구해라
단, 합을 구하기 전에 1,-1 또는 -1,1을 번갈아가면서 곱해준 후에 더해라

2. 접근방법
 매 수열의 최대 값을 저장하면서 계산하면 되는 것으로 보인다
현재 자신의 값과 이전에 저장한 최대값을 연산을 하면 최대값이 저장될 듯하다
이전에 연산한 내용을 저장하고 더 큰값이 나오면 처음부터 연산하는 과정을 떠올려 DP를 적용해봤다
점화식 Math.max(sequence[i] * (-1 or 1), dp[i - 1] + sequence[i] * (-1 or 1));

3. 구현과정

long answer = Integer.MIN_VALUE;
long[] dp1 = new long[sequence.length];
long[] dp2 = new long[sequence.length];
int[] pulse = {1, -1};

answer에 최대값을 저장하고 출력하기 위해 최소값으로 설정
pulse의 순서가 -1, 1, -1 과 1, -1, 1 순으로 진행하기에 메모이제이션을 위한 dp배열을 두개 생성

for (int i = 0; i < sequence.length; i++) {
	if (i == 0) dp1[i] = sequence[i] * pulse[i % 2];
	else {
		dp1[i] = Math.max(sequence[i] * pulse[i % 2], dp1[i - 1] + (sequence[i] * pulse[i % 2]));
	}
}
for (int i = 0; i < sequence.length; i++) {
	if (i == 0) dp2[i] = sequence[i] * pulse[(i + 1) % 2];
	else {
		dp2[i] = Math.max(sequence[i] * pulse[(i + 1) % 2], dp2[i - 1] + (sequence[i] * pulse[(i + 1) % 2]));
	}
}

두가지 pulse 순서에 따른 반복문
첫번째 반복문은 pulse의 i%2 값 두번째 반복문은 (i+1) %2 값을 해서 서로 반대되는 연산 진행

for(int i = 0; i < sequence.length; i++){
    answer = Math.max(answer, dp1[i]);
    answer = Math.max(answer, dp2[i]);
}

최대값 탐색

4.결과