Problem Brief

Efficient Deployments

INTERNOA

See Snowflake online assessment and hiring insights

A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends upon the order of deployment of its adjacent processors.

For the i th processor, the efficiency of the i th processor is no_adjacent[i], one_adjacent[i], or both_adjacent[i] when neither, one, or both adjacent processors are deployed before processor i.

Note: The 1st and n th processors can only have one adjacent.

Find the maximum possible sum of efficiencies amongst all possible orders of deployment.

Function Description

Complete the function getMaximumSum in the editor.

getMaximumSum has the following parameters:

1. int no_adjacent[n]: an array of integers
2. int one_adjacent[n]: an array of integers
3. int both_adjacent[n]: an array of integers

Returns

long integer: the maximum possible sum of efficiencies

࣪𓏲ּ ᥫ᭡ Credit to Defthobo 🌟𓂃

1Example 1

Input

no_adjacent = [1, 2, 3, 4], one_adjacent = [4, 4, 2, 1], both_adjacent = [0, 1, 1, 0]

Output

Explanation

Consider the following orders of deployment (1-based indexing): 1. The deployment sequence is (1 -> 3 -> 4 -> 2). Then, the sequence of efficiencies is no_adjacent[1] + no_adjacent[3] + one_adjacent[4] + both_adjacent[2] = 1 + 3 + 1 + 1 = 6. 2. Let the deployment sequence be (4 -> 2 -> 1 -> 3), no_adjacent[4] + no_adjacent[2] + one_adjacent[1] + both_adjacent[3] = 4 + 2 + 4 + 1 = 11. 3. Result should be (4 -> 3 -> 2 -> 1), no_adjacent[4] + one_adjacent[3] + one_adjacent[2] + one_adjacent[1] = 4 + 2 + 4 + 4 = 14 Similarly, other deployment orders can be performed. Amongst all possible deployments, the maximum possible sum of efficiencies is 14.

Constraints

Limits and guarantees your solution can rely on.

2 <= n <= 10^5
1 <= no_adjacent[i], one_adjacent[i], both_adjacent[i] <=10^9