โปรแกรมค้นหาผลรวมค่าสัมบูรณ์ที่อยู่ติดกันสูงสุดหลังจากการกลับรายการครั้งเดียวใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และเราสามารถย้อนกลับรายการย่อยในรายการได้ครั้งเดียว หลังจากดำเนินการนี้แล้ว เราต้องหาค่าสูงสุดที่เป็นไปได้ของ

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

ดังนั้นหากอินพุตเป็น nums =[2, 4, 6] ผลลัพธ์จะเป็น 6 เช่นเดียวกับเมื่อเราย้อนกลับ [4, 6] เราจะได้รายการเป็น [2, 6, 4] และค่า | 2 − 6| + |6 − 4| =6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้าขนาดของ nums <=1 แล้ว −

  • คืนค่า 0

• ตอบ :=0

• n :=ขนาดของ nums

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

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

• ต้นฉบับ :=ans

• สำหรับการเริ่มต้น 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 :=−|nums[1] − nums[0]|

• pm :=−|nums[1] − nums[0]|

• mp :=−|nums[1] − nums[0]|

• มม. :=−|nums[1] − nums[0]|

• สำหรับการเริ่มต้น 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