กำหนดอาร์เรย์ arr[] ที่มีสมาชิกเป็นจำนวนเต็ม เป้าหมายคือนับจำนวน subsequence แบบคณิตศาสตร์ (Arithmetic Progression - AP) ภายใน arr[] ช่วงของสมาชิกใน arr[] อยู่ระหว่าง [1, 1000000]
ลำดับว่างเปล่าหรือลำดับที่มีสมาชิกเพียงตัวเดียวก็จะถูกนับด้วย
ทำความเข้าใจด้วยตัวอย่าง
ตัวอย่าง
Input - arr[] = {1, 2, 3}
Output - จำนวน AP Subsequences ในอาร์เรย์คือ: 8
คำอธิบาย - Subsequence ต่อไปนี้เป็น AP:
{}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}
Input - arr[] = {2, 4, 5, 8}
Output - จำนวน AP Subsequences ในอาร์เรย์คือ: 12
คำอธิบาย - Subsequence ต่อไปนี้เป็น AP:
{}, {2}, {4}, {5}, {8}, {2, 4}, {2, 5}, {2, 8}, {4, 5}, {4, 8}, {5, 8}, {2, 5, 8}
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- ลำดับว่างเปล่าก็เป็น AP
- ค่าเดี่ยวก็เป็น AP
- หาค่าต่ำสุดและสูงสุดในอาร์เรย์เป็น max_val และ min_val ความต่างร่วม (common difference) ของ subsequence AP ทั้งหมดจะอยู่ในช่วง [min_val - max_val, max_val - min_val]
- สำหรับแต่ละความต่างร่วม เราจะหา subsequence โดยใช้ dynamic programming และเก็บไว้ใน arr_2[size]
- ไม่มี subsequence ที่มีความยาว 2 หรือมากกว่า 2 จะเป็นผลรวมของ arr_2[i] - 1 โดยที่ i คือ [0, 2] และความต่างคือ D
- arr_2[i] = 1 + sum(arr[j]) โดยที่ i < j และ arr_2[j] + D = arr_2[i]
- เพื่อวิธีที่เร็วกว่า ให้บวกผลรวม (arr_2[j] ที่มี arr[j] + D = arr[i] และ j < i) ใน arr_3[max_size]
- รับอาร์เรย์จำนวนเต็ม arr[] เป็นอินพุต
- ฟังก์ชัน AP_subsequence(int arr[], int size) รับอาร์เรย์อินพุตและคืนค่าจำนวน AP Subsequences ในอาร์เรย์
- กำหนดค่า count เริ่มต้นเป็น 0
- กำหนดตัวแปร max_val, min_val, arr_2[size] สำหรับเก็บจำนวน subsequence และ arr_3[max_size] สำหรับเก็บผลรวม
- วนลูปผ่าน arr[] ด้วย for loop และหาสมาชิกสูงสุดและต่ำสุด เก็บไว้ใน max_val และ min_val
- กำหนด count = size + 1 สำหรับ AP ที่มีสมาชิกเดี่ยวและ AP ว่างเปล่า
- คำนวณความต่างสูงสุด diff_max = max_val - min_val และ diff_min = min_val - max_val เป็นความต่างร่วมที่เป็นไปได้
- วนลูปด้วย for loop จาก j = 0 ถึง j < size
- กำหนด arr_2[j] = 1
- สำหรับ arr[j] - i >= 1 และ arr[j] - i <= 1000000 ให้ arr_2[j] += arr_3[arr[j] - i]
- บวก arr_2[j] - 1 เข้าไปใน count
- อัปเดตผลรวมเป็น arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j]
- ในที่สุดคืนค่า count เป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define max_size 10000
int AP_subsequence(int arr[], int size) {
int count = 0;
int max_val = INT_MAX;
int min_val = INT_MIN;
int arr_2[size];
int arr_3[max_size];
for (int i = 0; i < size; i++) {
max_val = min(max_val, arr[i]);
min_val = max(min_val, arr[i]);
}
count = size + 1;
int diff_max = max_val - min_val;
int diff_min = min_val - max_val;
for (int i = diff_max; i <= diff_min; i++) {
memset(arr_3, 0, sizeof arr_3);
for (int j = 0; j < size; j++) {
arr_2[j] = 1;
if (arr[j] - i >= 1) {
if (arr[j] - i <= 1000000) {
arr_2[j] += arr_3[arr[j] - i];
}
}
count += arr_2[j] - 1;
arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j];
}
}
return count;
}
int main() {
int arr[] = {1, 1, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of AP (Arithmetic Progression) Subsequences in an array are: " << AP_subsequence(arr, size);
return 0;
}
หากเรารันโค้ดข้างต้น จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Count of AP (Arithmetic Progression) Subsequences in an array are: 17
