C++에서 배열의 AP(산술 진행) 하위 시퀀스 수

<시간/>

정수 요소를 포함하는 배열 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 ]
이제 각 공통 차이점에 대해 동적 프로그래밍을 사용하여 하위 시퀀스를 찾고 rr_2[크기]에 저장합니다.
길이가 2 또는 2보다 큰 부분 시퀀스는 arr_2[i]-1의 합이 되지 않습니다. 여기서 i는 [0,2]이고 차이는 D입니다.
arr_2[i] =1+ 합계 ( arr[j] ) 여기서 i
더 빠른 접근을 위해 arr_3[max_size]에 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] 변수를 사용합니다.
for 루프를 사용하여 arr[]을 탐색하고 최대 및 최소 요소를 찾아 max_val 및 min_val에 저장합니다.
단일 요소 AP 및 빈 AP에 대해 개수 =크기 +1을 사용합니다.
최대 차이 diff_max =max_val - min_val 및 diff_min =min_val - max_val을 가능한 공통 차이로 계산합니다.
for 루프를 사용하여 j=0에서 j 까지 순회
arr_2[j] =1로 설정
arr[j] - i>=1 및 arr[j] - i <=1000000의 경우 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