Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 부분 리스트 한 번 반전 후 인접 요소 절대값 차이의 최대 합 구하기

문제 개요

숫자 리스트 nums가 주어지고, 리스트 안에서 임의의 부분 리스트(sublist)를 최대 한 번 반전(뒤집기)할 수 있다고 가정해 보겠습니다. 이 연산을 수행한 후, 아래 식으로 표현되는 값의 최댓값을 구하는 것이 목표입니다.

Σi=0n−2 |nums[i+1] − nums[i]|

예를 들어 입력이 nums = [2, 4, 6]이라면 결과는 6입니다. [4, 6] 구간을 반전하면 리스트가 [2, 6, 4]가 되고, 이때 |2 − 6| + |6 − 4| = 6이 되기 때문입니다.

해결 전략

이 문제는 모든 반전 구간을 일일이 시도하는 대신, 수학적 분석을 통해 선형 시간에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 먼저 반전을 하지 않은 상태의 인접 요소 절대값 차이 총합을 계산하여 orig에 저장합니다.
  • 반전 구간이 배열의 양 끝(첫 번째 또는 마지막 요소)에 닿는 경우를 먼저 처리합니다. i번째 요소와 경계 요소 사이의 차이 변화를 계산해 최댓값을 갱신합니다.
  • 반전 구간이 배열 내부에 완전히 포함되는 경우에는 네 개의 상태 변수 pp, pm, mp, mm를 사용합니다. 이들은 각각 ±nums[j−1], ±nums[j]의 부호 조합에 대해 지금까지의 최적 이득 값을 추적합니다.
  • 매 위치 j에서 새로운 반전 후보를 평가하고, 네 가지 조합 중 최댓값으로 ans를 갱신합니다.

알고리즘 단계

  • 리스트의 크기가 1 이하이면 0을 반환합니다.
  • ans를 0으로 초기화하고, n은 리스트의 크기로 설정합니다.
  • i = 1부터 n−1까지 순회하며 |nums[i] − nums[i−1]|을 ans에 누적합니다.
  • orig에 현재 총합을 저장합니다.
  • i = 1부터 n−2까지 순회하며 경계 반전 두 가지 경우를 비교합니다.
    • orig − |nums[i] − nums[i+1]| + |nums[0] − nums[i+1]|
    • orig − |nums[i] − nums[i−1]| + |nums[n−1] − nums[i−1]|
  • pp, pm, mp, mm을 −|nums[1] − nums[0]|과 nums[0], nums[1]의 부호 조합으로 초기화합니다.
  • j = 2부터 n−2까지 순회하며 내부 반전 후보를 평가하고 상태 변수를 함께 갱신합니다.
  • 최종 ans를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
    if (nums.size() <= 1)
    return 0;
    int ans = 0;
    int n = nums.size();
    for (int i = 1; i < n; i++) {
       ans += abs(nums[i] − nums[i − 1]);
    }
    int orig = ans;
    for (int i = 1; i < n − 1; i++) {
       ans = max(ans, orig − abs(nums[i] − nums[i + 1]) +
       abs(nums[0] − nums[i + 1]));
       ans = max(ans, orig − abs(nums[i] − nums[i − 1]) + abs(nums[n
    − 1] − nums[i − 1]));
    }
    int pp = −abs(nums[1] − nums[0]) + nums[0] + nums[1];
    int pm = −abs(nums[1] − nums[0]) + nums[0] − nums[1];
    int mp = −abs(nums[1] − nums[0]) − nums[0] + nums[1];
    int mm = −abs(nums[1] − nums[0]) − nums[0] − nums[1];
    for (int j = 2; j < n − 1; j++) {
       int jerror = abs(nums[j + 1] − nums[j]);
       ans = max(ans, orig + pp − jerror − nums[j] − nums[j + 1]);
       ans = max(ans, orig + pm − jerror − nums[j] + nums[j + 1]);
       ans = max(ans, orig + mp − jerror + nums[j] − nums[j + 1]);
       ans = max(ans, orig + mm − jerror + nums[j] + nums[j + 1]);
       pp = max(pp, −abs(nums[j] − nums[j − 1]) + nums[j − 1] +
       nums[j]);
       pm = max(pm, −abs(nums[j] − nums[j − 1]) + nums[j − 1] −
       nums[j]);
       mp = max(mp, −abs(nums[j] − nums[j − 1]) − nums[j − 1] +
       nums[j]);
       mm = max(mm, −abs(nums[j] − nums[j − 1]) − nums[j − 1] −
       nums[j]);
    }
    return ans;
}
int main(){
    vector<int> v = {2, 4, 6};
    cout << solve(v);
}

입력

{2, 4, 6}

출력

6

복잡도 분석

이 알고리즘은 리스트를 상수 번 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 변수가 상수 개수이므로 공간 복잡도 역시 O(1)입니다. 모든 가능한 반전 구간을 직접 시도하는 O(n²) 완전 탐색 방식보다 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.