FastPrep

Description

Solutions

Efficient Deployments 🌨️

🤘 INTERN📚RELATED PROBLEMS

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 is deployed before processor i.

Note: The 1^st 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 maxEfficiency in the editor.

maxEfficiency has the following parameters:

int noAdjacent[n]: an array of integers

int oneAdjacent[n]: an array of integers

int bothAdjacent[n]: an array of integers

Returns

long_int: the maximum possible sum of efficiencies

Example 1:

Input:  noAdjacent = [1, 2, 3, 4], oneAdjacent = [4, 4, 2, 1], bothAdjacent = [0, 1, 1, 0]
Output: 13 
Explanation:
Consider the following orders of deployment (1-based indexing):

 The deployment sequence is {1 → 3 → 4 → 2}. Then, the sum of efficiencies = no_adjacent[1] + no_adjacent[3] + one_adjacent[4] + both_adjacent[2] = 1 + 3 + 1 + 1 = 6.
  
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.
  
Let the deployment sequence be {4 → 3 → 2 → 1}, one_adjacent[3] + one_adjacent[2] + 2 + 2 + 4 + 1 = 7.

Similarly, other deployment orders can be performed.
       
Amongst all possible deployments, the maximum possible sum of efficiencies is 13.

Example 2:

Input:  noAdjacent = [2, 1, 3], oneAdjacent = [4, 2, 1], bothAdjacent = [1, 2, 3]
Output: 9 
Explanation:
Several ways to deploy processors are:

let dethe deployment sequence be {1 -> 2 -> 3}
   * The sum of efficiencies = no_adjacent[1] + one_adjacent[2] ++ 2 + 1 = 5

{1 -> 3 -> 2_, no_adjacent[1] + no_adjacent[3] + both_adjacent[2] = 2 + 3 + 2 = 7

{2 -> 1 -> 3}, no_adjacent[2] + one_adjacent[1] ++ 4 + 1 = 6

{2 -> 3 -> 1}, no_adjacent[2] + one_adjacent[3] ++ 1 + 4 = 6

{3 -> 2 -> 1}, no_adjacent[3] + one_adjacent[2] ++ 2 + 4 = 9

{3 -> 1 -> 2}, no_adjacent[3] + no_adjacent[1] + both_adjacent[2] = 3 + 2 + 2 = 7

Example 3:

Input:  noAdjacent = [1, 6], oneAdjacent = [2, 3], bothAdjacent = [3, 2]
Output: 8 
Explanation:
Some ways to deploy processors are:

Let the deployment sequence be {1 -> 2}. Then, sum of efficiencies = no_adjacent[1] ++ 3 = 4

{2 -> 1}, no_adjacent[2] ++ 2 = 8

Constraints:

1 <= n <= 10⁵

1 <= no_adjacent[i], one_adjacent[i], both_adjacent[i] <= 10⁹