연속 펄스 부분 수열의 합
문제 풀이 시간 : 1시간
문제 요약
- •
정수 수열
sequence가 주어짐
- •
연속된 일부 구간(부분 수열)을 선택하고 같은 길이의 펄스 수열을 각 원소에 곱함
- •
펄스 수열은 두 가지 형태 중 하나
- ◦
[1, -1, 1, -1, …]
- ◦
[-1, 1, -1, 1, …]
- •
곱셈 결과로 만들어진 연속 펄스 부분 수열의 합 중 가장 큰 값을 구하기
문제 풀이
처음 이 문제를 보고 부분 합을 구해야겠다는 생각을 하고 일단 1로 시작하는 펄스 수열과 -1로 시작하는 펄스 수열을 각각 곱해서 순차합을 구해보았다.
예시와 같이 [2, 3, -6, 1, 3, -1, 2, 4] 라는 수열이 있을 때, 1과 -1로 시작하는 펄스 수열을 곱하면 아래와 같다.
- •
1로 시작하는 펄스 수열을 곱한 경우 :
[2, -3, -6, -1, 3, 1, 2, -4]
- •
1로 시작하는 펄스 수열을 곱한 경우 :
[-2, 3, 6, 1, -3, -1, -2, 4]
그리고 각 수열의 순차 합은 아래와 같다.
- •
1로 시작하는 펄스 수열을 곱한 경우 :
[2, -1, -7, -8, -5, -4, -2, -6]
- •
1로 시작하는 펄스 수열을 곱한 경우 :
[-2, 1, 7, 8, 5, 4, 2, 6]
이 두가지 수열을 자세히 살펴보면 그냥 부호가 반대이고 동일한 수열인 것을 알 수 있다!
그래서 우리는 한가지 경우에 대해서만 계산하고 절댓값을 통해 최대 부분 수열의 합을 구할 수 있다.
그러면 이제 최대 부분 수열의 합을 구하는 것이 문제인데
이건 아주 쉽다.
우리는 이미 연속된 부분 수열의 합을 구해두었기 때문에 그런 부분 수열의 합 중에서 가장 큰 것과 작은 것을 빼주면 되는 것이다.
위의 1로 시작하는 펄스 수열에서 가장 큰 값은 2이고, 가장 작은 값은 -8 이므로 두가지 값을 빼주면 10이라는 최댓값이 나오게 된다.
초기 코드
import java.util.*;
class Solution {
public long solution(int[] sequence) {
long answer = 0;
int len = sequence.length;
long[] sum = new long[len+1];
sum[0] = sequence[0];
sum[len] = 0;
for(int i=1;i<len;i++){
if(i%2==0)
sum[i] = sum[i-1]+sequence[i];
else
sum[i] = sum[i-1]-sequence[i];
}
Arrays.sort(sum);
answer = sum[len] - sum[0];
return answer;
}
}처음엔 위와 같이 코드를 작성했다.
물론 이 코드도 동작하고 통과하는 코드이지만 생각해보니 이렇게 sum 배열을 계산하고, 정렬을 하는 불필요한 동작이 필요가 없었다!
최종 코드
class Solution {
public long solution(int[] sequence) {
long answer = 0;
int len = sequence.length;
long max = 0L;
long min = 0L;
long sum = 0L;
for(int i=0;i<len;i++){
if(i%2==0)
sum += sequence[i];
else
sum -= sequence[i];
max = Math.max(max, sum);
min = Math.min(min, sum);
}
return max - min;
}
}
또 다른 풀이
이 문제는 당연히 다른 방식으로도 풀 수 있다.
부분 수열의 합을 구하는 방법에는 Kadane 알고리즘이 있다.
Kadane 알고리즘 코드
class Solution {
public long solution(int[] sequence) {
long answer = 0L;
long dp0 = 0L; // 1로 시작하는 펄스수열을 곱한 수열의 최대 부분합
long dp1 = 0L; // -1로 시작하는 펄스수열을 곱한 수열의 최대 부분합
for (int i = 0; i < sequence.length; i++) {
if ((i & 1) == 0) { // 짝수 인덱스
dp0 = Math.max(0L, dp0) + sequence[i];
dp1 = Math.max(0L, dp1) - sequence[i];
} else { // 홀수 인덱스
dp0 = Math.max(0L, dp0) - sequence[i];
dp1 = Math.max(0L, dp1) + sequence[i];
}
answer = Math.max(answer, Math.max(dp0, dp1));
}
return answer;
}
}