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.
这道 Amazon OA 题的核心是：把若干个月的 PnL 取反后，仍要保证任意前缀和始终严格大于 0，同时让负数月数尽可能多。由于原数组全为正数，最优策略不是随意翻转，而是沿着前缀和贪心地维护当前已经翻成负数的元素集合；当某个前缀和会变得不合法时，就尝试把之前选过的“绝对值更大”的正贡献换成更小的负贡献，从而释放前缀空间。实现上通常使用前缀和配合大根堆 / 优先队列，在线扫描数组并动态调整已选择的翻转项，最终堆中保留的元素个数就是答案。这个思路能在 O(n log n) 内完成，适合 n 很大的 OA 场景。
