C++で開始値と終了値が同じになるような最大合計サブ配列

このチュートリアルでは、開始値と終了値が同じになるように最大合計サブアレイを見つけるプログラムについて説明します。

このために、整数を含む配列が提供されます。私たちのタスクは、要素の両端が等しくなるように合計が最大になるサブ配列を見つけることです。

例

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

出力

37