C++에서 주어진 배열에 대한 모든 고유 하위 배열 합계의 합계 찾기

이 문제에서는 n개의 정수 값으로 구성된 배열 arr[]이 제공됩니다. 우리의 임무는 주어진 배열에 대한 모든 고유한 하위 배열 합계를 찾는 것입니다. . 부분배열 합은 주어진 부분배열의 요소들의 합입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : arr[] = {1, 2, 4}
Output : 23

설명 -

All subarrays of the given array are :
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
Sum of subarrays = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

솔루션 접근 방식

문제에 대한 해결책은 하위 배열 합계를 저장한 다음 고유한 항목을 찾기 위해 정렬하는 것입니다. 그런 다음 합계에 대해 모든 고유한 하위 배열을 고려합니다.

알고리즘

1단계 − 모든 하위 배열의 합을 찾아 벡터에 저장합니다.

2단계 − 벡터를 정렬합니다.

3단계 − 고유한 모든 벡터를 고려하고 나머지 합계를 0으로 표시합니다.

4단계 − 합계를 계산하고 인쇄합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int i, j;
   long int sumArrayTill[n + 1] = { 0 };
   for (i = 0; i < n; i++)
      sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
   vector<long int> subArraySum;
   for (i = 1; i <= n; i++)
      for (j = i; j <= n; j++)
        subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
   sort(subArraySum.begin(), subArraySum.end());
   for (i = 0; i < subArraySum.size() - 1; i++){
      if (subArraySum[i] == subArraySum[i + 1]) {
         j = i + 1;
         while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){
            subArraySum[j] = 0; j++;
         }
         subArraySum[i] = 0;
      }
   }
   long sum = 0;
   for (i = 0; i < subArraySum.size(); i++)
      sum += subArraySum[i];
   return sum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

출력

The sum of all unique subarray sum is 144

반복을 사용한 또 다른 접근 방식

문제를 해결하는 또 다른 방법은 해시 테이블을 사용하는 것입니다. 우리는 하위 배열 합계를 찾아 해시 테이블에 저장하고 해시 수를 증가시킵니다. 그런 다음 모든 고유한 하위 배열(해시 카운트가 1인 하위 배열)의 합계를 찾습니다.

예시

솔루션 작동을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int sumSubArraySum = 0;
   unordered_map<int, int> sumSubArray;
   for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
         sum += arr[j];
         sumSubArray[sum]++;
      }
   }
   for (auto itr : sumSubArray)
      if (itr.second == 1)
         sumSubArraySum += itr.first;
      return sumSubArraySum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

출력

The sum of all unique subarray sum is 124