FastPrep
Problem · Dynamic Programming

Maximum Charge After Removal

Learn this problem
● HardAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

Select a system and remove it, causing the neighboring systems to automatically merge and combine their charge values. If the removed system has neighboring systems with charges x and y directly to its 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 this 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 and 5th 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

maximumChargeAfterRemoval(charge: int[]) → int

Complete the function maximumChargeAfterRemoval in the editor.

maximumChargeAfterRemoval has the following parameter:

  1. int[] charge: an array of integers representing the charges

Returns

int: the maximum possible charge of the remaining system

Examples

Example 1

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

One way the engineers can remove the system charges is as follows:

Index of the charge removed(0-indexed) New state of charges

[4, 3, -2, 1] -> [4, 4]

[4, 4] -> [4]

The maximum possible charge of the remaining system is 4.

Constraints

🐱🐱

More Amazon problems

drafts saved locally
public int maximumChargeAfterRemoval(int[] charge) {
  // write your code here
}
charge[-2, 4, 3, -2, 1]
expected4
checking account