Trong bài toán này, chúng ta đưa ra một mảng arr [] có kích thước n gồm các giá trị dương. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng tối đa các phân thức con có giá trị bắt đầu và giá trị kết thúc giống nhau.
Mô tả sự cố - Ở đây, chúng ta cần tìm một mảng con sao cho các phần tử ở chỉ mục i (chỉ mục bắt đầu của mảng con) và j (chỉ số kết thúc của mảng con) giống nhau tức là arr [i] =arr [j]. Và tổng các phần tử của mảng con được tối đa hóa.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {2, 1, 3, 5, 6, 2, 4, 3} Đầu ra
23
Giải thích
All subarrays which are starting and ending with the same element are:
{2, 1, 3, 5, 6, 2} = 2 + 1 + 3 + 5 + 6 + 2 = 19
{3, 5, 6, 2, 4, 3} = 3 + 5 + 6 + 2 + 4 + 3 = 23 Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng ta cần xem xét thực tế rằng đối với giá trị dương, tổng của các mảng con tăng lên cùng với kích thước của các mảng con mà chúng ta xem xét. Forthis, chúng ta sẽ tìm thấy mảng con có kích thước tối đa bằng cách tìm lần xuất hiện ngoài cùng bên trái và ngoài cùng bên phải của các số trong mảng. Và trả lại số tiền của họ nếu số tiền lớn hơn tối đa.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#include <bits/stdc++.h>
using namespace std;
int maxValue(int arr[], int n) {
unordered_map<int, int> startIndex, endIndex;
int sumArr[n];
sumArr[0] = arr[0];
for (int i = 1; i < n; i++) {
sumArr[i] = sumArr[i − 1] + arr[i];
if (startIndex[arr[i]] == 0)
startIndex[arr[i]] = i;
endIndex[arr[i]] = i;
}
int maxSum = 0;
for (int i = 0; i < n; i++) {
int left = startIndex[arr[i]];
int right = endIndex[arr[i]];
maxSum = max(maxSum, sumArr[right] − sumArr[left − 1]);
}
return maxSum;
}
int main() {
int arr[] = { 2, 1, 3, 5, 6, 2, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum sum subarray such that start and end values are same is "<<maxValue(arr, n);
return 0;
} Đầu ra
The maximum sum subarray such that start and end values are same is 23