Coding Question 2
The Supply chain manager of one of Amazon's warehouses wants to measure efficiency of the way parcles are shipped .There are n parcles presented in the array "parcle_weights".Each day, the manager can pick parcles in that array until all are shipped and none remain.
The manager computesthe sum of parcle weights shipped each day before shipping any parcle in the warehouse. This sum is called warehouse efficiency. Each day before shipping any parcle in the warehouse,this efficiency is calculated and added to the sum of total efficiency of the warehouse.
Given the array "parcle_weights", find the maximun possible efficiency of the warehouse.
Example 1
n=6
parcle_weights=[4,4,8,5,3,2]
| Day | Parcels | Parcel Picked | Total Efficiency |
|---|---|---|---|
| 1 | [4, 4, 8, 5, 3, 2] | 1st with size 4 | 4 |
| 2 | [4, 8, 5, 3, 2] | 3rd with size 5 | 9 |
| 3 | [8, 5] | 1st with size 8 | 17 |
| 4 | [] | No parcel left to ship | 17 |
| Hence, the answer is 17. It can be shown that the answer cannot be greater than 17. | |||
| Example 2 | |||
| n=7 | |||
| parcle_weights=[2,1,8,5,6,2,4] |
| Day | Parcels | Parcel Picked (case 1) | Total (case 1) | Parcel Picked (case 2) | Total (case 2) |
|---|---|---|---|---|---|
| 1 | [2, 1, 8, 5, 6, 2, 4] | 4 | 4 | 4 | 4 |
| 2 | [1, 8, 5, 6, 2] | 2 | 6 | 6 | 10 |
| 3 | [8, 5, 6] | 8 | 14 | 8 | 18 |
| 4 | [5] | 5 | 19 | 5 | 23 |
| 5 | [] | No parcel left to ship | 19 | No parcel left to ship | 23 |
In case 1, the order of picked parcels would produce an answer of 4 + 2 + 8 + 5 = 19, which is incorrect. The correct selection of parcels would be in scenario 2, where the answer will be 4 + 6 + 8 + 5 = 23.
Constraints
- 1<=n<=2x10^5
- 0<=parcle_weights[i]<=10^9