Tìm tổng tất cả tổng con mảng duy nhất cho mảng cho trước trong C++

Trong bài toán này, chúng ta được cho một mảng arr[] gồm n giá trị nguyên. Nhiệm vụ của chúng ta là tìm tổng của tất cả tổng con mảng duy nhất cho một mảng cho trước. Tổng con mảng là tổng các phần tử của con mảng đó.

Hãy xem ví dụ sau để hiểu bài toán:

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

Giải thích −

Tất cả các con mảng của mảng cho trước: (1), (2), (4), (1, 2), (2, 4), (1, 2, 4) Tổng các con mảng = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

Phương pháp giải

Một giải pháp là lưu trữ tổng con mảng và sắp xếp để tìm các giá trị duy nhất. Sau đó ta chỉ xét các con mảng duy nhất cho tổng.

Thuật toán

Bước 1 − Tìm tổng của tất cả các con mảng và lưu vào vector.

Bước 2 − Sắp xếp vector.

Bước 3 − Xét các vector duy nhất và gán tổng còn lại bằng 0.

Bước 4 − Tính và in tổng.

Ví dụ

Chương trình minh họa cho giải pháp

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

Kết quả

The sum of all unique subarray sum is 144

Phương pháp khác sử dụng Lặp

Một phương pháp khác để giải bài toán là sử dụng bảng băm. Ta sẽ tìm các tổng con mảng và lưu vào bảng băm, tăng đếm. Sau đó tìm tổng tất cả các con mảng duy nhất (con mảng với đếm băm = 1).

Ví dụ

Chương trình minh họa cho giải pháp

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

Kết quả

The sum of all unique subarray sum is 124