C++에서 단일 반전 후 최대 인접 절대값 합을 찾는 프로그램

num이라는 숫자 목록이 있고 목록의 하위 목록을 최대 한 번만 뒤집을 수 있다고 가정합니다. 이 작업을 수행한 후 가능한 최대값

$\displaystyle\sum\limits_{i=0}^{n-2}| 숫자[i+1]-[숫자[i]|$

따라서 입력이 nums =[2, 4, 6]과 같으면 출력은 6이 됩니다. [4, 6]을 반대로 하면 목록이 [2, 6, 4]로 표시되고 값 | 2 - 6| + |6 − 4| =6

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 숫자의 크기가 <=1이면 -

  • 0 반환

• 답변 :=0

• n :=숫자 크기

• initialize i :=1의 경우, i

  • ans :=ans + |nums[i] − nums[i − 1]|

• 원본 :=및

• initialize i :=1의 경우, i

  • ans :=ans와 orig의 최대값 − |(nums[i] − nums[i + 1]| + |nums[0] − nums[i + 1]|

  • ans :=ans와 orig의 최대값 − |(nums[i] − nums[i − 1]| + |nums[n − 1] − nums[i − 1]|

• pp :=-|숫자[1] - 숫자[0]|

• 오후 :=-|숫자[1] - 숫자[0]|

• mp :=-|숫자[1] - 숫자[0]|

• mm :=-|숫자[1] - 숫자[0]|

• initialize j :=2의 경우 j

  • jerror :=|nums[j + 1] - nums[j]|

  • ans :=ans의 최대값 및 (orig + pp − jerror − nums[j] − nums[j + 1])

  • ans :=ans의 최대값 및 (orig + pm − jerror − nums[j] + nums[j + 1])

  • ans :=ans의 최대값 및 (orig + mp − jerror + nums[j] − nums[j + 1])

  • ans :=ans의 최대값 및 (orig + mm − jerror + nums[j] + nums[j + 1])

  • pp :=pp 및 -|nums[j] − nums[j − 1]|

    의 최대값

  • pm :=pm 및 -|nums[j] − nums[j − 1]|

    의 최대값

  • mp :=mp 및 -|nums[j] − nums[j − 1]|

    의 최대값

  • mm :=mm 및 -|nums[j] − nums[j − 1]|

    의 최대값

• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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