สมมติว่าเรามีอาร์เรย์จำนวนเต็มหนึ่งชุดที่เรียกว่า nums ค่าของอาร์เรย์นี้ถูกกำหนดเป็นผลรวมของ |nums[i]-nums[i+1]| สำหรับ i ทั้งหมดในช่วง 0 ถึง n - 1 โดยที่ n คือขนาดของอาร์เรย์ เราสามารถเลือก subarray ของอาร์เรย์ที่กำหนดและย้อนกลับได้ เราสามารถดำเนินการนี้ได้เพียงครั้งเดียว จากนั้นเราต้องหาค่าสูงสุดของอาร์เรย์สุดท้าย
ดังนั้น หากอินพุตเป็น [1,5,4,2,3] ผลลัพธ์จะเป็น 10
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ret :=0, พิเศษ :=0
-
n :=ขนาดของ nums
-
minVal :=inf, maxVal :=-inf
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
a :=nums[i], b :=nums[i + 1]
-
ret :=ret + |b - a|
-
พิเศษ :=สูงสุดของพิเศษ และ |(nums[0] - b) - |a - b||
-
พิเศษ :=สูงสุดของพิเศษ และ |(nums[n - 1] - a) - |a - b||
-
maxVal :=สูงสุดของ maxVal และต่ำสุดของ a และ b
-
minVal :=ขั้นต่ำของ minVal และสูงสุดของ a และ b
-
-
return ret + สูงสุดของ extra และ (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} ผลลัพธ์
10
