ค่าสูงสุดของ |arr[0] – arr[1] - + |arr[1] – arr[2] - + … +|arr[n – 2] – arr[n – 1] - เมื่อองค์ประกอบมีค่าตั้งแต่ 1 ถึง n ใน C++

ในปัญหานี้ เราจะได้รับอาร์เรย์จำนวนเต็ม n ตัวของช่วง [1,n] งานของเราคือสร้างโปรแกรมที่จะหาค่าสูงสุดของ |arr[0] – arr[1] - + |arr[1] – arr[2] - + … +|arr[n – 2] – arr[ น – 1].

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − array={1, 2, 3}

ผลผลิต − 3

คำอธิบาย −

max sum is
|1-3|+|2-1| = 3

ในการแก้ปัญหานี้ วิธีง่ายๆ คือการสร้างพีชคณิตทั้งหมดจากอาร์เรย์ และหาค่าสูงสุดของค่าทั้งหมดจากการเรียงสับเปลี่ยน วิธีที่มีประสิทธิภาพมากขึ้นคือการสรุปค่าสูงสุดทั้งหมดสำหรับแต่ละค่าของ n แล้วสร้างสูตรทั่วไป

ดังนั้น

Maximum sum for (n = 1) = 0
Maximum sum for (n = 2) = 1
Maximum sum for (n = 3) = 3
Maximum sum for (n = 4) = 7
Maximum sum for (n = 5) = 11
So, the maximum value is 0, 1, 3, 7, 11…

สูตรทั่วไปคือ ((n*n/2)-1)

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int maxAbsVal(int n) {
   if (n == 1)
      return 0;
   return ((n*n/2) - 1);
}
int main() {
   int n = 4;
   cout<<"The maximum sum of absolute difference is "<<maxAbsVal(n);
   return 0;
}

ผลลัพธ์

The maximum sum of absolute difference is 7