เราได้รับอาเรย์ที่เป็น permutation ของจำนวนธรรมชาติ 1 ถึง N เป้าหมายคือหาคู่ index (i, j) ที่ทำให้เงื่อนไข: Arr[i] + Arr[j] = max(Arr[x]) สำหรับ i ≤ x ≤ j นั่นคือ ผลรวมของ Arr[i] และ Arr[j] เท่ากับค่าสูงสุดที่เกิดขึ้นระหว่างช่วง i ถึง j
อินพุต
Arr[] = {2, 4, 1, 3, 6, 5}
เอาต์พุต
Count of index pairs which satisfy the given condition: 1
คำอธิบาย − คู่ที่ทำให้เงื่อนไข: 1+5=6, 6 อยู่ระหว่าง 1 และ 5 และเป็นค่าสูงสุดในช่วง → 1 คู่
อินพุต
Arr[] = {1, 2, 5, 4, 3}
เอาต์พุต
Count of index pairs which satisfy the given condition: 2
คำอธิบาย − 1+4=5 (5 อยู่ระหว่าง 1,4 และเป็น max), 2+3=5 (5 อยู่ระหว่าง 2,3 และเป็น max) → 2 คู่
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ Arr[] และ size
- ฟังก์ชัน countPairs(int A[], int n) คืนค่าจำนวนคู่
- count = 0, max1 = A[0], maxindex = 0
- ลูป i=0..n-2, j=i+1..n-1 อัปเดต max1 และ maxindex หาก A[j] >= max1
- ถ้า A[i]+A[j] == max1 และ maxindex อยู่ระหว่าง i และ j ให้ count++
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int countPairs(int A[], int n) {
int count = 0;
int max1 = A[0];
int maxindex = 0;
for (int i = 0; i < n-1; i++) {
for (int j = i+1; j < n; j++) {
if (A[j] >= max1) {
max1 = A[j];
maxindex = j;
}
if (A[i] + A[j] == max1 && maxindex >= i && maxindex <= j)
count++;
}
}
return count;
}
int main() {
int Arr[] = {3, 4, 6, 1, 5, 2};
int size = 6;
cout << endl << "Count of index pairs which satisfy the given condition: "
<< countPairs(Arr, size);
return 0;
}
ผลลัพธ์
Count of index pairs which satisfy the given condition: 1
