You are analyzing the market trends of Amazon stocks. An AWS financial service model returned an array of integers, PnL (Profit and Loss), for your portfolio, representing the gain or loss in each month. All reported PnL values are positive, representing gains.
As part of the analysis, you will perform the following operation on the PnL array any number of times:
- Choose any month
i(0 <= i < n) and multiplyPnL[i]by-1.
Find the maximum number of months you can afford to have a negative PnL such that the cumulative PnL for each of the n months remains strictly positive.
Note: The cumulative PnL for the i-th month is defined as the sum of PnL from the starting month up to the i-th month.
Example
Consider n = 4 and PnL = [5, 3, 1, 2].
Some possible arrays after performing the operation some number of times:
[5, -3, -1, 2]→ cumulative PnL =[5, 2, 1, 3], number of negatives =2, valid[5, -3, -1, -2]→ cumulative PnL =[5, 2, 1, -1], number of negatives =3, invalid[5, -3, 1, -2]→ cumulative PnL =[5, 2, 3, 1], number of negatives =2, valid[-5, 3, 1, 2]→ cumulative PnL =[-5, -2, -1, 1], number of negatives =1, invalid
There are many more ways to perform the operations, but the maximum number of negative PnLs while maintaining a positive cumulative PnL is 2. Return 2 as the answer.
Function Description
Complete the function getMaxNegativePnL in the editor below.
getMaxNegativePnL has the following parameter:
int PnL[n]: an array of integers
Return
int: the maximum number of months that can be made negative while keeping every prefix sum strictly positive.
This Amazon OA problem asks for the maximum number of months that can be flipped negative while keeping every prefix sum strictly positive. The key is a greedy scan with a prefix sum and a max heap: whenever a flip would break the prefix constraint, you can reconsider earlier chosen flips and replace a larger impact item with a smaller one if it helps preserve positivity. The final heap size gives the answer, and the approach runs efficiently in O(n log n).
