Given an array nums of size N which accommodates two varieties of numbers, one which has the worth zero, the second which is a optimistic integer, the duty is to gather numbers from the beneath operations and return the utmost worth you’ll be able to acquire.
- If the given quantity is a optimistic integer, then it’s your selection, whether or not you’ll be able to put it on the highest of the queue or not.
- Else, if the quantity is zero, then choose the topmost quantity from the queue and take away it.
Examples:
Enter: N = 7, nums = [1, 2, 3, 0, 4, 5, 0]
Output: 8
Clarification: To maximise the full worth do the next operation whereas iterating the nums[ ]:
nums[0] = 1, placed on the highest of the queue. Queue turns into: [1]
nums[1] = 2, placed on the highest of the queue. Queue turns into: [2, 1]
nums[2] = 3, placed on the highest of the queue. Queue turns into: [3, 2, 1]
nums[3] = 0, choose the highest worth from the queue and take away it. Complete val = 3, and queue turns into: [2, 1]
nums[4] = 4, placed on the highest of the queue. Queue turns into: [4, 2, 1]
nums[5] = 5, placed on the highest of the queue. Queue turns into: [5, 4, 2, 1]
nums[6] = 0, choose the highest worth from the queue and take away it. Complete val = 3 + 5 = 8, and queue turns into: [4, 2, 1]
Return val = 8.Enter: N = 8, nums = [5, 1, 2, 0, 0, 4, 3, 0]
Output: 11
Clarification: To maximise the full worth do the next operation whereas iterating the nums[ ]:
nums[0] = 5, placed on the highest of the queue. Queue turns into: [5]
nums[1] = 1, ignore this quantity. Queue stays: [5]
nums[2] = 2, placed on the highest of the queue. Queue turns into: [2, 5]
nums[3] = 0, choose the highest worth from the queue and take away it. Complete val = 0 + 2 = 2, and queue turns into: [5]
nums[4] = 0, choose the highest worth from the queue and take away it. Complete val = 2 + 5 = 7, and queue turns into: [ ]
nums[5] = 4, placed on the highest of the queue. Queue turns into: [4]
nums[6] = 3, ignore this quantity. Queue stays: [4]
nums[7] = 0, choose the highest worth from the queue and take away it. Complete val = 7 + 4 = 11, and queue turns into: [ ]
Return val = 11.
Method: To resolve the issue observe the beneath thought:
We’ll use a lowering precedence queue and retailer the optimistic integers in it, after we encounter zero we’ll take the peek() ingredient (if it’s not empty) from the precedence queue and add it to the variable val.
Beneath are the steps for the above method:
- Initialize a lowering precedence queue.
- Iterate the given array,
- Should you encounter any optimistic integer, add it to the precedence queue.
- Else, in case you encounter a zero, test whether or not the precedence queue is empty or not. If it’s not empty, take away the highest ingredient from it and add it to the variable val which accommodates the present sum of the utmost worth.
- Return the ultimate reply val.
Beneath is the code for the above method:
Java
|
|
Most worth is : 11
Time Complexity: O(N * log(N))
Auxiliary House: O(N)
