Citadel OA | Portfolio Balances | Citadel Online Assessment Question

An investor opens a new account and wants to invert in a number of assets. Each asset begins with a balance of 0, and its value is stored in an array using 1-based indexing. Periodically, a contribution is received and equal investments are made in a subset of the portfolio. Each contribution will be given by investment amount, start index, end index. Each investment in that range will receive the contribution amount. Determine the maximum amount invested in any one investment after all contributions.

This problem is same as Amazon Online Assessment 2021 (OA) - Investment Max Value.

Relevant Citadel OA Problems:

Input

n: the number of investments available
rounds: an [k][3] array of integers, each rounds[i] contains 3 integers, [left, right, contribution]

Output

the maximum invested in any one asset

Examples

Example 1:

Input:

1n = 5
2rounds = [[1, 2, 10], [2, 4, 5], [3, 5, 12]]

Output: 17

Explanation:

For example, start with an array of 5 elements: investments = [0,0,0,0,0]*. The variables left and right represent the starting and ending indices, inclusive. Another varible, contribution, is the new funds to invest per asset. The first investment is at index 1.

left	right	contribution	investments
			[0,0,0,0,0]
1	2	10	[10,10,0,0,0]
2	4	5	[10,15,5,5,0]
3	5	12	[10,15,17,17,12]

In the first round, a contribution of 10 is made to investment 1 and 2. In the second round, a contribution of 5 is made to assets 2,3 and 4. Finally, in the third round, a contribution of 12 is added to investments 3, 4 and 5.The maximum inverted in any one asset is 17.

*Note: The investments array is not provided in the function. It is to be created after the number of assets available is known.

Constraints

3<=n<=10^7
`1<=o<=2*10^5
1<=left<=right<=n
0<=contribution<=10^9