Maximize sum by selecting Array factor to left of every ‘1’ of a Binary String

[ad_1]

View Dialogue

Enhance Article

Save Article

Like Article

View Dialogue

Enhance Article

Save Article

Like Article

Given a binary string S and an array arr[] every of measurement N, we are able to choose any factor from the Array which is to the left of (or on the similar place) the indices of ‘1’s within the given binary string. The duty is to search out the utmost doable sum.

Examples:

Enter: arr[] = {20, 10, 30, 9, 20, 9}, string S = “011011”, N = 6
Output: 80
Rationalization: Choose 20, 10, 30 and 20 in Sum, so, Sum = 80.

Enter:  arr[] = {30, 20, 10}, string S = “000”, N = 3.
Output: 0

Strategy: The given downside could be solved through the use of a precedence queue based mostly on the next concept:

Say there are Ok occurrences of ‘1’ in string S. It may be seen that we are able to organize the characters in a approach such that we are able to choose the Ok most parts from the array that are to the left of the final incidence of ‘1’ in S. So we are able to use a precedence queue to get these Ok most parts.

Comply with the steps to unravel this downside:

  • Initialize variable Sum = 0, Cnt = 0.
  • Create a precedence queue (max heap) and traverse from i = 0 to N-1:
    • If S[i] is ‘1’, increment Cnt by 1.
    • Else, whereas Cnt > 0, add the topmost factor of the precedence queue and decrement Cnt by 1.
    • Push the ith factor of the array into the precedence queue.
  • After executing the loop, whereas Cnt > 0, add the topmost factor of the precedence queue and decrement Cnt by 1.
  • Eventually, return the Sum because the required reply.

Under is the implementation of the above method.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int findMaxSum(int* arr, string s, int n)

{

    

    int Cnt = 0, Sum = 0;

  

    priority_queue<int> pq;

  

    

    for (int i = 0; i < n; i++) {

        if (s[i] == '1') {

            Cnt++;

        }

        else {

            whereas (Cnt != 0) {

                Sum += pq.high();

                pq.pop();

                Cnt--;

            }

        }

  

        

        pq.push(arr[i]);

    }

  

    whereas (Cnt != 0) {

        Sum += pq.high();

        pq.pop();

        Cnt--;

    }

  

    

    return Sum;

}

  

int principal()

{

    int N = 6;

    string S = "011011";

    int arr[] = { 20, 10, 30, 9, 20, 9 };

  

    

    cout << findMaxSum(arr, S, N) << endl;

  

    return 0;

}

Time Complexity: O(N * log N)
Auxiliary House: O(N)

[ad_2]

Leave a Reply