How should I practice Maximum Possible Charge?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Maximum Possible Charge associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Maximum Possible Charge

Learn this problem

● HardAmazonOA

See Amazon hiring insights

Problem statement

A team of engineers at Amazon using advanced simulation tools, are analyzing a series of interconnected systems, where each system has a charge values represented by charge[] which can be positive, negative or zero.

The engineers have a specialised tool that allows them to perform the following operations: Select a system and remove it, causing the neighbouring systems to automatically merge and combine their charge values. If the removed system has neighbouring systems with charges x and y directly to it's left and right, they will combine to form a new system with charge x+y. No combination will take place if the system is the leftmost or rightmost in the array.

Since the process is computationally expensive, the engineers will simulate the operation using Amazon's advanced tools.

For example, if the system charges are [-3, 1, 4, -1, 5, -9], using the tool on the 4th system (index 3) will result in the new sequence [-3, 1, 9, -9] as the charges from the 3rd systems combine to 4 + 5 = 9. If they then use the tool on the 1st system in this new sequence, it will become [1, 9, -9].

The engineers will continue performing these operations until only one system remains.

Given an array charge of size n, find the maximum possible charge of the remaining system after performing these operations.

Function

maximumPossibleCharge(charge: int[]) → int

Examples

Example 1

charge = [-2, 4, 3, -2, 1]return = 4

By removing the 1st system (index 0), the array becomes [4, 3, -2, 1]. Then, removing the 3rd system (index 2) results in [4, 4, 1]. Finally, removing the 2nd system (index 1) leaves [4, 1], and removing the 1st system (index 0) results in the maximum possible charge of 4.

Example 2

charge = [-2, 4, 9, 1, -1]return = 9

By removing the 1st system (index 0), the array becomes [4, 9, 1, -1]. Then, removing the 3rd system (index 2) results in [4, 10, -1]. Finally, removing the 2nd system (index 1) leaves [4, -1], and removing the 1st system (index 0) results in the maximum possible charge of 9.

Example 3

charge = [-1, 3, 2]return = 3

By removing the 1st system (index 0), the array becomes [3, 2]. Then, removing the 1st system (index 0) results in the maximum possible charge of 3.

Constraints

1 <= n <= 2*10^5
-10^9 <= charge[i] <= 10^9