Đếm số dãy con cấp số cộng (AP) trong mảng bằng C++

Cho một mảng arr[] chứa các phần tử nguyên. Mục tiêu là đếm số lượng dãy con cấp số cộng (Arithmetic Progression - AP) bên trong arr[]. Phạm vi các phần tử trong arr[] là [1, 1000000].

Dãy rỗng hoặc dãy có một phần tử cũng được tính là AP.

Hiểu qua ví dụ

Ví dụ 1

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

Đầu ra: Số dãy con AP trong mảng là: 8

Giải thích: Các dãy con sau tạo thành AP:

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

Ví dụ 2

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

Đầu ra: Số dãy con AP trong mảng là: 12

Giải thích: Các dãy con sau 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 sử dụng

Dãy rỗng cũng là một AP.
Một giá trị đơn lẻ cũng là một AP.
Tìm giá trị nhỏ nhất và lớn nhất trong mảng là max_val và min_val. Các công sai trong tất cả các dãy con AP sẽ nằm trong khoảng [min_val - max_val, max_val - min_val].
Với mỗi công sai, chúng ta tìm các dãy con bằng quy hoạch động và lưu trữ trong arr_2[size].
Không có dãy con độ dài 2 hoặc lớn hơn 2 sẽ là tổng của arr_2[i] - 1 với i trong [0, 2] và công sai là D.
arr_2[i] = 1 + sum(arr_2[j]) với i < j và arr_2[j] + D = arr_2[i].
Để tối ưu hơn, cộng dồn tổng (arr_2[j] với arr[j] + D = arr[i] và j < i) vào arr_3[max_size].
Nhập mảng nguyên arr[].
Hàm AP_subsequence(int arr[], int size) nhận mảng đầu vào và trả về số lượng dãy con AP.
Khởi tạo biến đếm ban đầu là 0.
Sử dụng các biến max_val, min_val, arr_2[size] để lưu số lượng dãy con và arr_3[max_size] để lưu tổng.
Duyệt arr[] bằng vòng lặp for để tìm phần tử lớn nhất, nhỏ nhất và lưu vào max_val, min_val.
Đặt count = size + 1 cho các AP đơn phần tử và AP rỗng.
Tính công sai tối đa diff_max = max_val - min_val và diff_min = min_val - max_val.
Duyệt bằng vòng lặp for từ j = 0 đến j < size.
Đặt arr_2[j] = 1.
Nếu arr[j] - i >= 1 và arr[j] - i <= 1000000 thì arr_2[j] += arr_3[arr[j] - i].
Cộng arr_2[j] - 1 vào count.
Cập nhật tổng: arr_3[arr[j]] = arr_3[arr[j]] + arr_2[j].
Cuối cùng trả về count.

Ví dụ mã nguồn

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

Chạy mã trên sẽ cho kết quả:

Kết quả

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