Maximize sum by picking Array element to left of each β1β of a Binary String
Given a binary string S and an array arr[] each of size N, we can pick any element from the Array which is to the left of (or at the same position) the indices of β1βs in the given binary string. The task is to find the maximum possible sum.
Examples:
Input: arr[] = {20, 10, 30, 9, 20, 9}, string S = β011011β, N = 6
Output: 80
Explanation: Pick 20, 10, 30 and 20 in Sum, so, Sum = 80.Input: arr[] = {30, 20, 10}, string S = β000β, N = 3.
Output: 0
Approach: The given problem can be solved by using a priority queue based on the following idea:
Say there are K occurrences of β1β in string S. It can be seen that we can arrange the characters in a way such that we can pick the K maximum elements from the array which are to the left of the last occurrence of β1β in S. So we can use a priority queue to get these K maximum elements.
Follow the steps to solve this problem:
- Initialize variable Sum = 0, Cnt = 0.
- Create a priority queue (max heap) and traverse from i = 0 to N-1:
- If S[i] is β1β, increment Cnt by 1.
- Else, while Cnt > 0, add the topmost element of the priority queue and decrement Cnt by 1.
- Push the ith element of the array into the priority queue.
- After executing the loop, while Cnt > 0, add the topmost element of the priority queue and decrement Cnt by 1.
- At last, return the Sum as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find maximum Sum int findMaxSum( int * arr, string s, int n) { // Initialize variables int Cnt = 0, Sum = 0; priority_queue< int > pq; // Traverse the string for ( int i = 0; i < n; i++) { if (s[i] == '1' ) { Cnt++; } else { while (Cnt != 0) { Sum += pq.top(); pq.pop(); Cnt--; } } // Push the element of array in pq pq.push(arr[i]); } while (Cnt != 0) { Sum += pq.top(); pq.pop(); Cnt--; } // Return Max Sum return Sum; } // Driver Code int main() { int N = 6; string S = "011011" ; int arr[] = { 20, 10, 30, 9, 20, 9 }; // Function Call cout << findMaxSum(arr, S, N) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.util.*; public class GFG { // Function to find maximum Sum static int findMaxSum( int [] arr, String s, int n) { // Initialize variables int Cnt = 0 , Sum = 0 ; PriorityQueue<Integer> pq = new PriorityQueue<Integer>( Collections.reverseOrder()); // Traverse the string for ( int i = 0 ; i < n; i++) { if (s.charAt(i) == '1' ) { Cnt++; } else { while (Cnt != 0 ) { Sum += pq.peek(); pq.poll(); Cnt--; } } // Push the element of array in pq pq.add(arr[i]); } while (Cnt != 0 ) { Sum += pq.peek(); pq.poll(); Cnt--; } // Return Max Sum return Sum; } // Driver Code public static void main(String[] args) { int N = 6 ; String S = "011011" ; int [] arr = { 20 , 10 , 30 , 9 , 20 , 9 }; // Function Call System.out.println(findMaxSum(arr, S, N)); return ; } } // This code is contributed by garg28harsh. |
Python3
# Python code to implement the approach import heapq # Function to find maximum Sum def findMaxSum(arr, s, n): # Initialize variables Cnt, Sum = 0 , 0 pq = [] heapq._heapify_max(pq) # Traverse the string for i in range (n): if (s[i] = = '1' ): Cnt + = 1 else : while (Cnt is not 0 ): Sum + = heapq.heappop(pq) heapq._heapify_max(pq) Cnt - = 1 # Push the element of array in pq heapq.heappush(pq, arr[i]) heapq._heapify_max(pq) while (Cnt is not 0 ): Sum + = heapq.heappop(pq) heapq._heapify_max(pq) Cnt - = 1 # Return Max Sum return Sum N = 6 S = "011011" arr = [ 20 , 10 , 30 , 9 , 20 , 9 ] # Function call print (findMaxSum(arr, S, N)) # This code is contributed by lokesh |
C#
// C# code to implement the approach using System; using System.Collections.Generic; using System.Linq; class Program { // Function to find maximum Sum static int findMaxSum( int [] arr, string s, int n) { // Initialize variables int Cnt = 0, Sum = 0; List< int > pq = new List< int >(); // Traverse the string for ( int i = 0; i < n; i++) { pq.Sort((a, b) => b.CompareTo(a)); if (s[i] == '1' ) { Cnt++; } else { while (Cnt != 0) { pq.Sort((a, b) => b.CompareTo(a)); Sum += pq[0]; pq.RemoveAt(0); Cnt--; } } // Push the element of array in pq pq.Add(arr[i]); } while (Cnt != 0) { pq.Sort((a, b) => b.CompareTo(a)); Sum += pq[0]; pq.RemoveAt(0); Cnt--; } // Return Max Sum return Sum; } // Driver Code public static void Main( string [] args) { int N = 6; string S = "011011" ; int [] arr = { 20, 10, 30, 9, 20, 9 }; // Function Call Console.WriteLine(findMaxSum(arr, S, N)); } } // This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Javascript code to implement the approach // Function to find maximum Sum function findMaxSum(arr, s, n) { // Initialize variables let Cnt = 0; let Sum = 0; pq=[]; // Traverse the string for (let i = 0; i < n; i++) { if (s[i] == '1' ) { Cnt++; } else { while (Cnt != 0) { Sum += pq[pq.length-1]; pq.pop(); Cnt--; } } // Push the element of array in pq pq.push(arr[i]); pq.sort((a,b)=>a-b); } while (Cnt != 0) { Sum += pq[pq.length-1]; pq.pop(); Cnt--; } // Return Max Sum return Sum; } // Driver Code let N = 6; let S = "011011" ; let arr = [ 20, 10, 30, 9, 20, 9 ]; // Function Call console.log(findMaxSum(arr, S, N)); // This code is contributed by Pushpesh Raj. |
80
Time Complexity: O(N * log N)
Auxiliary Space: O(N)