C++에서 배열 값을 최대화하기 위한 하위 배열 반전

nums라고 하는 하나의 정수 배열이 있다고 가정합니다. 이 배열의 값은 |nums[i]-nums[i+1]|의 합으로 정의됩니다. 범위 0에서 n - 1에 있는 모든 i에 대해. 여기서 n은 배열의 크기입니다. 주어진 배열의 하위 배열을 선택하고 반전할 수 있습니다. 이 작업은 한 번만 수행할 수 있습니다. 그런 다음 최종 배열의 가능한 최대값을 찾아야 합니다.

따라서 입력이 [1,5,4,2,3]과 같으면 출력은 10이 됩니다.

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

ret :=0, 추가 :=0
n :=숫자 크기
minVal :=inf, maxVal :=-inf
initialize i :=0의 경우, i
- a :=숫자[i], b :=숫자[i + 1]
- 렛 :=렛 + |b - a|
- extra :=extra 및 |(nums[0] - b) - |a - b||
  의 최대값
- extra :=extra의 최대값 및 |(nums[n - 1] - a) - |a - b||
- maxVal :=maxVal의 최대값과 b와 b의 최소값
- minVal :=minVal의 최소값 및 최대값 및 b
ret + 추가의 최대값 및 (maxVal - minVal) * 2를 반환

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

예시

#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}