문제 소개
정수 배열 nums가 있다고 가정해 봅시다. 이 배열의 '값'은 인접한 두 요소 차이의 절댓값을 모두 더한 합, 즉 0부터 n−2까지의 모든 i에 대한 |nums[i] − nums[i+1]|의 총합으로 정의됩니다. 여기서 n은 배열의 크기입니다.
우리는 이 배열에서 임의의 하위 배열(연속된 구간)을 하나 선택해 뒤집을 수 있으며, 이 반전 연산은 오직 한 번만 수행할 수 있습니다. 목표는 반전을 적용한 후 얻을 수 있는 최종 배열 값의 최댓값을 구하는 것입니다.
예를 들어 입력 배열이 [1, 5, 4, 2, 3]이라면, 적절한 구간을 반전했을 때의 최댓값은 10이 됩니다.
핵심 아이디어
하위 배열을 뒤집더라도 구간 내부의 인접 관계는 그대로 유지되며, 실제로 값이 변하는 지점은 반전 구간의 양쪽 경계에 있는 두 쌍뿐입니다. 따라서 전체 기본 합을 먼저 계산한 뒤, 반전을 통해 얻을 수 있는 '추가 이득(extra)'의 최댓값만 찾으면 됩니다.
추가 이득은 다음 두 가지 경우로 나누어 생각할 수 있습니다.
- 반전 구간이 배열의 끝에 맞닿은 경우: 구간이 배열의 시작 또는 끝에 붙어 있으면 새로 생기는 경계는 한쪽뿐입니다. 이때 이득은 |nums[0] − b| − |a − b| 또는 |nums[n−1] − a| − |a − b| 형태로 계산할 수 있습니다.
- 일반적인 경우: 각 인접 쌍 (a, b)에 대해 min(a, b)의 최댓값(maxVal)과 max(a, b)의 최솟값(minVal)을 추적하면, 이론상 가능한 최대 이득은 (maxVal − minVal) × 2가 됩니다.
알고리즘 단계
- ret := 0, extra := 0으로 초기화합니다.
- n := nums의 크기로 설정하고, minVal := 무한대, maxVal := −무한대로 초기화합니다.
- i를 0부터 n − 2까지 반복하면서 다음을 수행합니다.
- a := nums[i], b := nums[i + 1]
- ret := ret + |b − a| (기본 값 누적)
- extra := max(extra, |nums[0] − b| − |a − b|)
- extra := max(extra, |nums[n − 1] − a| − |a − b|)
- maxVal := max(maxVal, min(a, b))
- minVal := min(minVal, max(a, b))
- 최종적으로 ret + max(extra, (maxVal − minVal) × 2)를 반환합니다.
C++ 구현 예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxValueAfterReverse(vector<int>& nums) {
int ret = 0;
int extra = 0;
int n = nums.size();
int minVal = INT_MAX;
int maxVal = INT_MIN;
for(int i = 0; i < n - 1; i++){
int a = nums[i];
int b = nums[i + 1];
ret += abs(b - a);
extra = max(extra, abs(nums[0] - b) - abs(a - b));
extra = max(extra, abs(nums[n - 1] - a) - abs(a - b));
maxVal = max(maxVal, min(a, b));
minVal = min(minVal, max(a, b));
}
return ret + max(extra, (maxVal - minVal) * 2);
}
};
main(){
Solution ob;
vector<int> v = {1,5,4,2,3};
cout << (ob.maxValueAfterReverse(v));
}입력
{1,5,4,2,3}출력
10
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 배열의 크기가 매우 커도 효율적으로 동작하는 것이 이 방법의 가장 큰 장점입니다.