Đảo ngược mảng con để tối đa hóa giá trị mảng trong C ++

Giả sử chúng ta có một mảng số nguyên được gọi là nums. Giá trị của mảng này được định nghĩa là tổng của | nums [i] -nums [i + 1] | với mọi i trong phạm vi từ 0 đến n - 1. Trong đó n là kích thước của mảng. Chúng ta có thể chọn bất kỳ mảng con nào của mảng đã cho và đảo ngược nó. Chúng tôi chỉ có thể thực hiện thao tác này một lần. Sau đó, chúng ta phải tìm giá trị lớn nhất có thể có của mảng cuối cùng.

Vì vậy, nếu đầu vào là [1,5,4,2,3], thì đầu ra sẽ là 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, thêm:=0

• n:=kích thước của nums

• minVal:=inf, maxVal:=-inf

• để khởi tạo i:=0, khi tôi

  • a:=nums [i], b:=nums [i + 1]

  • ret:=ret + | b - a |

  • extra:=tối đa của extra và | (nums [0] - b) - | a - b ||

  • extra:=tối đa thêm và | (nums [n - 1] - a) - | a - b ||

  • maxVal:=tối đa là maxVal và tối thiểu là a và b

  • minVal:=tối thiểu là minVal và tối đa là a và b

• trả về ret + tối đa thêm và (maxVal - minVal) * 2

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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

Đầu vào

{1,5,4,2,3}

Đầu ra

10