Given an array nums of size N which comprises two kinds 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 may accumulate.
- If the given quantity is a optimistic integer, then it’s your alternative, whether or not you may put it on the highest of the queue or not.
- Else, if the quantity is zero, then decide 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 entire 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, decide 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, decide 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 entire 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, decide the highest worth from the queue and take away it. Complete val = 0 + 2 = 2, and queue turns into: [5]
nums[4] = 0, decide 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, decide the highest worth from the queue and take away it. Complete val = 7 + 4 = 11, and queue turns into: [ ]
Return val = 11.
Strategy: To unravel the issue comply with the beneath thought:
We’ll use a lowering precedence queue and retailer the optimistic integers in it, once we encounter zero we’ll take the peek() ingredient (if it isn’t empty) from the precedence queue and add it to the variable val.
Under are the steps for the above strategy:
- Initialize a lowering precedence queue.
- Iterate the given array,
- If you happen to encounter any optimistic integer, add it to the precedence queue.
- Else, for those who encounter a zero, test whether or not the precedence queue is empty or not. If it isn’t empty, take away the highest ingredient from it and add it to the variable val which comprises the present sum of the utmost worth.
- Return the ultimate reply val.
Under is the code for the above strategy:
Java
|
|
Most worth is : 11
Time Complexity: O(N * log(N))
Auxiliary Area: O(N)
