Maximum possible sum of a window in an array such that elements of same window in other array are unique in c++

Question

---

In this tutorial, we will be discussing a program to find maximum possible sum of a window in an array such that elements of same window in other array are unique.

For this we will be provided with two arrays with equal number of elements. Our task is to find the window in one element with maximum sum such that the same window in other array is unique.

Example

 Live Demo

#include <bits/stdc++.h>
using namespace std;
//returning maximum sum window
int returnMaxSum(int A[], int B[], int n) {
   //storing elements with their count
   unordered_set<int> mp;
   int result = 0;
   int curr_sum = 0, curr_begin = 0;
   for (int i = 0; i < n; ++i) {
      while (mp.find(A[i]) != mp.end()) {
         mp.erase(A[curr_begin]);
         curr_sum -= B[curr_begin];
         curr_begin++;
      }
      mp.insert(A[i]);
      curr_sum += B[i];
      result = max(result, curr_sum);
   }
   return result;
}
int main() {
   int A[] = { 0, 1, 2, 3, 0, 1, 4 };
   int B[] = { 9, 8, 1, 2, 3, 4, 5 };
   int n = sizeof(A)/sizeof(A[0]);
   cout << returnMaxSum(A, B, n);
   return 0;
}

Output

20

Ayush Gupta

Published on 09-Sep-2020 12:41:24