FastPrep
Problem · Dynamic Programming

Efficient Deployments

Learn this problem
● HardMeeshoFULLTIMEOA

Problem statement

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 on whether its adjacent processors have already been deployed.

For processor i, its efficiency is:

  • noAdjacent[i] if neither adjacent processor has been deployed before it.
  • oneAdjacent[i] if exactly one adjacent processor has been deployed before it.
  • bothAdjacent[i] if both adjacent processors have been deployed before it.

The first and nth processors only have one adjacent processor.

Return the maximum possible sum of efficiencies among all possible deployment orders.

Function

getMaximumEfficiency(noAdjacent: int[], oneAdjacent: int[], bothAdjacent: int[]) → long

Complete the function getMaximumEfficiency.

  • int[] noAdjacent: efficiency values when no adjacent processor was deployed first.
  • int[] oneAdjacent: efficiency values when one adjacent processor was deployed first.
  • int[] bothAdjacent: efficiency values when both adjacent processors were deployed first.

Returns

long: the maximum possible efficiency sum.

Examples

Example 1

noAdjacent = [1, 2, 3, 4]oneAdjacent = [4, 4, 2, 1]bothAdjacent = [1, 1, 1, 1]return = 14

One optimal deployment order is 4 -> 3 -> 2 -> 1. The efficiency sum is noAdjacent[4] + oneAdjacent[3] + oneAdjacent[2] + oneAdjacent[1] = 4 + 2 + 4 + 4 = 14.

Constraints

  • noAdjacent.length == oneAdjacent.length == bothAdjacent.length
  • n >= 1

More Meesho problems

drafts saved locally
public long getMaximumEfficiency(int[] noAdjacent, int[] oneAdjacent, int[] bothAdjacent) {
  // write your code here
}
noAdjacent[1, 2, 3, 4]
oneAdjacent[4, 4, 2, 1]
bothAdjacent[1, 1, 1, 1]
expected14
checking account