Sunday, October 23, 2022
HomeWordPress DevelopmentMaximize sum by selecting Array aspect to left of every '1' of...

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


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 aspect from the Array which is to the left of (or on the identical place) the indices of ‘1’s within the given binary string. The duty is to search out the utmost attainable 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

Method: The given drawback might be solved through the use of a precedence queue primarily based on the next thought:

Say there are Okay occurrences of ‘1’ in string S. It may be seen that we are able to prepare the characters in a means such that we are able to choose the Okay most components 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 Okay most components.

Comply with the steps to resolve this drawback:

  • 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 aspect of the precedence queue and decrement Cnt by 1.
    • Push the ith aspect of the array into the precedence queue.
  • After executing the loop, whereas Cnt > 0, add the topmost aspect of the precedence queue and decrement Cnt by 1.
  • Eventually, return the Sum because the required reply.

Beneath 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.prime();

                pq.pop();

                Cnt--;

            }

        }

  

        

        pq.push(arr[i]);

    }

  

    whereas (Cnt != 0) {

        Sum += pq.prime();

        pq.pop();

        Cnt--;

    }

  

    

    return Sum;

}

  

int essential()

{

    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 Area: O(N)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments