Given two arrays A and B of equal number of elements. The task is to find the maximum sum possible of a window in array B such that elements of same window in A[] are unique.
Examples:
Input: A = [0, 1, 2, 3, 0, 1, 4]
B = [9, 8, 1, 2, 3, 4, 5]
Output: sum = 20
The maximum sum possible in B[] such that
all corresponding elements in A[] are unique
is (9+8+1+2) = 20.
Input: A = [0, 1, 2, 0, 2]
B = [5, 6, 7, 8, 2]
Output: sum = 21
A simple solution is to consider all sub-arrays of B[]. For every sub-array, check if elements same sub-array in A[] are distinct or not. If distinct, then compare sum with result and update result.
C++
// C++ program to find the maximum// possible sum of a window in one// array such that elements in same// window of other array are unique.#include <bits/stdc++.h>using namespace std;// Function to return maximum sum of window// in B[] according to given constraints.int returnMaxSum(int A[], int B[], int n){ int result = INT_MIN; for (int i = 0; i < n; i++) { unordered_map<int, int> unmap; int sum = 0; for (int j = i; j < n; j++) { unmap[A[j]]++; sum += B[j]; if (unmap.size() == (j - i + 1)) { result = max(result, sum); } } } return result;}// Driver codeint 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;} |
Java
import java.util.HashMap;import java.util.Map;public class Gfg { static int returnMaxSum(int[] A, int[] B, int n) { int result = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { Map<Integer, Integer> unmap = new HashMap<>(); int sum = 0; for (int j = i; j < n; j++) { unmap.put(A[j], unmap.getOrDefault(A[j], 0) + 1); sum += B[j]; if (unmap.size() == (j - i + 1)) { result = Math.max(result, sum); } } } return result; } public static void main(String[] args) { int[] A = { 0, 1, 2, 3, 0, 1, 4 }; int[] B = { 9, 8, 1, 2, 3, 4, 5 }; int n = A.length; System.out.println(returnMaxSum(A, B, n)); }} |
C#
using System;using System.Collections.Generic;class Gfg { static int returnMaxSum(int[] A, int[] B, int n) { int result = int.MinValue; for (int i = 0; i < n; i++) { Dictionary<int, int> unmap = new Dictionary<int, int>(); int sum = 0; for (int j = i; j < n; j++) { if (!unmap.ContainsKey(A[j])) unmap.Add(A[j], 1); else unmap[A[j]]++; sum += B[j]; if (unmap.Count == (j - i + 1)) { result = Math.Max(result, sum); } } } return result; } public static void Main() { int[] A = { 0, 1, 2, 3, 0, 1, 4 }; int[] B = { 9, 8, 1, 2, 3, 4, 5 }; int n = A.Length; Console.WriteLine(returnMaxSum(A, B, n)); }} |
Python3
# Python program to find the maximum# possible sum of a window in one# array such that elements in same# window of other array are unique.import sys# Function to return maximum sum of window# in B[] according to given constraints.def returnMaxSum(A, B, n): result = -sys.maxsize for i in range(n): unmap = {} sum = 0 for j in range(i, n): if A[j] in unmap: unmap[A[j]] += 1 else: unmap[A[j]] = 1 sum += B[j] if len(unmap) == (j - i + 1): result = max(result, sum) return result# Driver codeif __name__ == '__main__': A = [0, 1, 2, 3, 0, 1, 4] B = [9, 8, 1, 2, 3, 4, 5] n = len(A) print(returnMaxSum(A, B, n)) |
Javascript
// JavaScript equivalent of the above code// Function to return maximum sum of window// in B[] according to given constraints.function returnMaxSum(A, B, n) { let result = -Number.MAX_VALUE; for (let i = 0; i < n; i++) { let unmap = {}; let sum = 0; for (let j = i; j < n; j++) { if (A[j] in unmap) { unmap[A[j]] += 1; } else { unmap[A[j]] = 1; } sum += B[j]; if (Object.keys(unmap).length == (j - i + 1)) { result = Math.max(result, sum); } } } return result;}// Driver code A = [0, 1, 2, 3, 0, 1, 4]; B = [9, 8, 1, 2, 3, 4, 5]; n = A.length; console.log(returnMaxSum(A, B, n)); |
Output
20
Time Complexity: O(n2), as we will be using nested loops for checking every sub-array.
Auxiliary Space: O(1), as we are not using any extra space.
An efficient solution is to use hashing.
- Create an empty hash table.
- Traverse array elements. Do following for every element A[i].
- While A[i] is present in hash table, keep removing elements from beginning of current window and keep subtracting window beginning element of B[] from current sum.
- Add B[i] to current sum and update result if current sum becomes more.
- Return result.
Below is the implementation of above steps.
C++
// C++ program to find the maximum// possible sum of a window in one// array such that elements in same// window of other array are unique.#include <bits/stdc++.h>using namespace std;// Function to return maximum sum of window// in B[] according to given constraints.int returnMaxSum(int A[], int B[], int n){ // Map is used to store elements // and their counts. unordered_set<int> mp; int result = 0; // Initialize result // calculating the maximum possible // sum for each subarray containing // unique elements. int curr_sum = 0, curr_begin = 0; for (int i = 0; i < n; ++i) { // Remove all duplicate // instances of A[i] in // current window. while (mp.find(A[i]) != mp.end()) { mp.erase(A[curr_begin]); curr_sum -= B[curr_begin]; curr_begin++; } // Add current instance of A[i] // to map and to current sum. mp.insert(A[i]); curr_sum += B[i]; // Update result if current // sum is more. result = max(result, curr_sum); } return result;}// Driver codeint 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;} |
Java
// Java program to find the maximum// possible sum of a window in one// array such that elements in same// window of other array are unique.import java.util.HashSet;import java.util.Set;public class MaxPossibleSuminWindow{ // Function to return maximum sum of window // in A[] according to given constraints. static int returnMaxSum(int A[], int B[], int n) { // Map is used to store elements // and their counts. Set<Integer> mp = new HashSet<Integer>(); int result = 0; // Initialize result // calculating the maximum possible // sum for each subarray containing // unique elements. int curr_sum = 0, curr_begin = 0; for (int i = 0; i < n; ++i) { // Remove all duplicate // instances of A[i] in // current window. while (mp.contains(A[i])) { mp.remove(A[curr_begin]); curr_sum -= B[curr_begin]; curr_begin++; } // Add current instance of A[i] // to map and to current sum. mp.add(A[i]); curr_sum += B[i]; // Update result if current // sum is more. result = Integer.max(result, curr_sum); } return result; } //Driver Code to test above method public static void main(String[] args) { int A[] = { 0, 1, 2, 3, 0, 1, 4 }; int B[] = { 9, 8, 1, 2, 3, 4, 5 }; int n = A.length; System.out.println(returnMaxSum(A, B, n)); }}// This code is contributed by Sumit Ghosh |
Python3
# Python3 program to find the maximum # possible sum of a window in one # array such that elements in same # window of other array are unique. # Function to return maximum sum of window # in B[] according to given constraints. def returnMaxSum(A, B, n): # Map is used to store elements # and their counts. mp = set() result = 0 # Initialize result # calculating the maximum possible # sum for each subarray containing # unique elements. curr_sum = curr_begin = 0 for i in range(0, n): # Remove all duplicate instances # of A[i] in current window. while A[i] in mp: mp.remove(A[curr_begin]) curr_sum -= B[curr_begin] curr_begin += 1 # Add current instance of A[i] # to map and to current sum. mp.add(A[i]) curr_sum += B[i] # Update result if current # sum is more. result = max(result, curr_sum) return result # Driver code if __name__ == "__main__": A = [0, 1, 2, 3, 0, 1, 4] B = [9, 8, 1, 2, 3, 4, 5] n = len(A) print(returnMaxSum(A, B, n))# This code is contributed by Rituraj Jain |
C#
// C# program to find the maximum// possible sum of a window in one// array such that elements in same// window of other array are unique. using System;using System.Collections.Generic;public class MaxPossibleSuminWindow{ // Function to return maximum sum of window // in A[] according to given constraints. static int returnMaxSum(int []A, int []B, int n) { // Map is used to store elements // and their counts. HashSet<int> mp = new HashSet<int>(); int result = 0; // Initialize result // calculating the maximum possible // sum for each subarray containing // unique elements. int curr_sum = 0, curr_begin = 0; for (int i = 0; i < n; ++i) { // Remove all duplicate // instances of A[i] in // current window. while (mp.Contains(A[i])) { mp.Remove(A[curr_begin]); curr_sum -= B[curr_begin]; curr_begin++; } // Add current instance of A[i] // to map and to current sum. mp.Add(A[i]); curr_sum += B[i]; // Update result if current // sum is more. result = Math.Max(result, curr_sum); } return result; } // Driver Code public static void Main(String[] args) { int []A = { 0, 1, 2, 3, 0, 1, 4 }; int []B = { 9, 8, 1, 2, 3, 4, 5 }; int n = A.Length; Console.WriteLine(returnMaxSum(A, B, n)); }} /* This code has been contributed by PrinciRaj1992*/ |
Javascript
<script>// Javascript program to find the maximum// possible sum of a window in one// array such that elements in same// window of other array are unique.// Function to return maximum sum of window// in B[] according to given constraints.function returnMaxSum(A, B, n){ // Map is used to store elements // and their counts. var mp = new Set(); var result = 0; // Initialize result // calculating the maximum possible // sum for each subarray containing // unique elements. var curr_sum = 0, curr_begin = 0; for (var i = 0; i < n; ++i) { // Remove all duplicate // instances of A[i] in // current window. while (mp.has(A[i])) { mp.delete(A[curr_begin]); curr_sum -= B[curr_begin]; curr_begin++; } // Add current instance of A[i] // to map and to current sum. mp.add(A[i]); curr_sum += B[i]; // Update result if current // sum is more. result = Math.max(result, curr_sum); } return result;}// Driver codevar A = [0, 1, 2, 3, 0, 1, 4];var B = [9, 8, 1, 2, 3, 4, 5];var n = A.length;document.write( returnMaxSum(A, B, n));// This code is contributed by importantly.</script> |
Output
20
Time Complexity: O(n), as we are using a loop to traverse N times and unordered map operations will take constant time. Where N is the number of elements in the array.
Auxiliary Space: O(N), as we are using extra space for the map. Where N is the number of elements in the array.
Note that every element of array is inserted and removed at most once from array.
This article is contributed by Parth Trehan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
