Mảng con tổng tối đa sao cho giá trị bắt đầu và giá trị kết thúc giống nhau trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm mảng con có tổng tối đa sao cho giá trị bắt đầu và giá trị kết thúc giống nhau.

Đối với điều này, chúng ta sẽ được cung cấp một mảng chứa các số nguyên. Nhiệm vụ của chúng ta là tìm mảng con có tổng lớn nhất sao cho các phần tử ở hai đầu của nó đều bằng nhau.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//finding the maximum sum
int maxValue(int a[], int n) {
   unordered_map<int, int> first, last;
   int pr[n];
   pr[0] = a[0];
   for (int i = 1; i < n; i++) {
      pr[i] = pr[i - 1] + a[i];
      if (first[a[i]] == 0)
         first[a[i]] = i;
      last[a[i]] = i;
   }
   int ans = 0;
   for (int i = 0; i < n; i++) {
      int start = first[a[i]];
      int end = last[a[i]];
      ans = max(ans, pr[end] - pr[start - 1]);
   }
   return ans;
}
int main() {
   int arr[] = { 1, 3, 5, 2, 4, 18, 2, 3 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << maxValue(arr, n);
   return 0;
}

Đầu ra

37