Đếm chuỗi con AP (Tiến trình số học) trong một mảng trong C ++

Cho một mảng arr [] chứa các phần tử nguyên. Mục đích là để đếm số lượng các dãy con của Cấp số học bên trong arr []. Phạm vi của các phần tử bên trong arr [] là [1.1000000].

Chuỗi trống hoặc phần tử đơn lẻ cũng sẽ được tính.

Hãy cho chúng tôi hiểu với các ví dụ.

Ví dụ

Đầu vào - arr [] ={1,2,3}

Đầu ra - Số lượng AP (Tiến trình số học) Các chuỗi con trong một mảng là:8

Giải thích - Các chuỗi con sau sẽ tạo thành AP:-

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

Đầu vào - arr [] ={2,4,5,8}

Đầu ra - Số lượng AP (Tiến trình số học) Các chuỗi con trong một mảng là:12

Giải thích - Các chuỗi con sau sẽ tạo thành AP:-

{}, {2}, {4}, {5}, {8}, {2,4}, {2,5}, {2,8}, {4,5}, {4,8}, { 5,8}, {2,5,8}

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Một chuỗi trống cũng là một AP.
Một giá trị duy nhất cũng là một AP.
Tìm các giá trị tối thiểu và lớn nhất trong mảng dưới dạng max_val và min_val. Sự khác biệt phổ biến trong tất cả các chuỗi con AP sẽ nằm giữa [min_val - max_val, max_val - min_val]
Bây giờ đối với mỗi điểm khác biệt chung, chúng tôi sẽ tìm các chuỗi con bằng cách sử dụng lập trình động và lưu trữ trong arr_2 [size].
Không có dãy con nào có độ dài 2 hoặc nhiều hơn 2 sẽ là tổng của arr_2 [i] -1 trong đó i là [0,2] và hiệu là D.
arr_2 [i] =1+ sum (arr [j]) trong đó tôi
Để có cách tiếp cận nhanh hơn, hãy thêm các tổng (arr_2 [j] với arr [j] + D =arr [i] và j
Lấy mảng số nguyên arr [] làm đầu vào.
Hàm AP_subsequence (int arr [], int size) nhận một mảng đầu vào và trả về số lượng các Chuỗi con AP (Tiến trình số học) trong một mảng.
Lấy số lượng ban đầu là 0.
Lấy các biến max_val, min_val, arr_2 [size] để lưu trữ số lượng dãy con và arr_3 [max_size] để lưu trữ tổng.
Traverse arr [] bằng cách sử dụng vòng lặp for và tìm phần tử tối đa và tối thiểu và lưu trữ trong max_val và min_val.
Lấy count =size +1 cho các AP phần tử đơn lẻ và AP trống.
Tính toán chênh lệch tối đa diff_max =max_val - min_val và diff_min =min_val - max_val như những khác biệt chung có thể.
Duyệt bằng vòng lặp for từ j =0 đến j
Đặt arr_2 [j] =1;
Đối với arr [j] - i> =1 và arr [j] - i <=1000000, đặt arr_2 [j] + =arr_3 [arr [j] - i].
Thêm arr_2 [j] -1 để đếm.
Cập nhật tổng dưới dạng arr_3 [arr [j]] =arr_3 [arr [j]] + arr_2 [j].
Kết quả là số lượt trả lại cuối cùng.

Ví dụ

#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;
}

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Đầu ra

Count of AP (Arithmetic Progression) Subsequences in an array are: 17