ค่าสูงสุดของ |arr[i] – arr[j] - + |i

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

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

ป้อนข้อมูล − อาร์เรย์ ={4, 1, 2}

ผลผลิต − 4

คำอธิบาย −

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

ในการแก้ปัญหานี้ วิธีง่ายๆ ก็คือการใช้ กำลังเดรัจฉาน วิธีการซึ่งจะใช้สองลูปและค้นหาความแตกต่างสูงสุด

แต่แนวทางที่มีประสิทธิภาพจะใช้คุณสมบัติของฟังก์ชันสัมบูรณ์

มาถอดรหัสสมการและหาคำตอบกัน

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}

อันที่หนึ่งและอันที่หนึ่งเหมือนกัน อันที่สองและอันที่สี่เหมือนกัน เมื่อใช้สิ่งนี้ เราจะสร้างสองอาร์เรย์ที่จะเก็บค่า arr[i]+- i.

array1 จะเก็บค่า arr[i] + i

array2 จะเก็บค่า arr[i] - i

ดังนั้นเราจะหาค่าสูงสุดได้สองค่าคือ

สูงสุด ((max(array1)-min(array1)), (max(array2)-min(array2)))

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
   int ans = 0;
   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
   return ans;
}
int main() {
   int array[] = { 5, 7, 1, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   cout<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
   return 0;
}

ผลลัพธ์

The maximum value of |arr[i] - arr[j]| + |i-j| is 7

ค่าสูงสุดของ |arr[i] – arr[j] - + |i – j| ใน C++

ตัวอย่าง

ผลลัพธ์