จำนวนของ AP (ความก้าวหน้าทางคณิตศาสตร์) ที่ตามมาในอาร์เรย์ใน C++

รับอาร์เรย์ arr[] ที่มีองค์ประกอบจำนวนเต็ม เป้าหมายคือการนับจำนวนลำดับย่อยของความก้าวหน้าทางคณิตศาสตร์ภายใน arr[] ช่วงขององค์ประกอบภายใน arr[] คือ [1,1000000].

ลำดับที่ว่างเปล่าหรือองค์ประกอบเดียวจะถูกนับด้วย

ให้เราเข้าใจด้วยตัวอย่าง

ตัวอย่าง

ป้อนข้อมูล - arr[] ={1,2,3}

ผลลัพธ์ - จำนวน AP (ความก้าวหน้าทางคณิตศาสตร์) ที่ตามมาในอาร์เรย์คือ:8

คำอธิบาย - ลำดับต่อไปนี้จะสร้าง AP:-

{}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

ป้อนข้อมูล - arr[] ={2,4,5,8}

ผลลัพธ์ - จำนวน AP (ความก้าวหน้าทางคณิตศาสตร์) ที่ตามมาในอาร์เรย์คือ:12

คำอธิบาย - ลำดับต่อไปนี้จะสร้าง 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 ความแตกต่างทั่วไปในลำดับย่อย AP ทั้งหมดจะอยู่ระหว่าง [ min_val - max_val , max_val - min_val ]
• ตอนนี้ สำหรับความแตกต่างทั่วไปแต่ละรายการ เราจะพบส่วนย่อยโดยใช้การเขียนโปรแกรมแบบไดนามิกและจัดเก็บใน arr_2[ขนาด]
• ลำดับย่อยของความยาว 2 หรือมากกว่า 2 จะไม่เป็นผลรวมของ arr_2[i]-1 โดยที่ i คือ [0,2] และผลต่างคือ D
• arr_2[i] =1+ ผลรวม ( arr[j] ) โดยที่ i
• สำหรับวิธีที่เร็วกว่า ให้บวกผลรวม ( arr_2[j] กับ arr[j]+D =arr[i] และ j
• รับอาร์เรย์จำนวนเต็ม arr[] เป็นอินพุต
• ฟังก์ชัน AP_subsequence(int arr[], int size) รับอาร์เรย์อินพุตและส่งกลับจำนวน AP (ความก้าวหน้าทางคณิตศาสตร์) ในอาร์เรย์
• นับเริ่มต้นเป็น 0
• นำตัวแปร max_val, min_val, arr_2[size] เพื่อจัดเก็บการนับลำดับและ arr_3[max_size] สำหรับเก็บผลรวม
• Traverse arr[] ใช้ for loop และค้นหาองค์ประกอบสูงสุดและต่ำสุดและเก็บไว้ใน max_val และ min_val
• นับจำนวน =ขนาด +1 สำหรับ AP องค์ประกอบเดียวและ AP ที่ว่างเปล่า
• คำนวณความแตกต่างสูงสุด diff_max =max_val - min_val และ diff_min =min_val - max_val เป็นความแตกต่างทั่วไปที่เป็นไปได้
• สำรวจโดยใช้ for loop จาก j=0 ถึง j
• ตั้งค่า arr_2[j] =1;
• สำหรับ arr[j] - i>=1 และ arr[j] - i <=1000000 set arr_2[j] +=arr_3[arr[j] - i].
• เพิ่ม arr_2[j]-1 เพื่อนับ
• อัปเดตผลรวมเป็น arr_3[arr[j]] =arr_3[arr[j]] + arr_2[j].
• เมื่อสิ้นสุดการส่งคืน นับเป็นผลลัพธ์

#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