FastPrep
Problem · Array

Maximize Protected City Population

● MediumAmazonFULLTIMEOA
See Amazon hiring insights

You are given n cities arranged in a line. City i has population population[i] and may contain a security unit described by unit[i], where unit[i] = '1' means a unit is initially stationed in city i.

Each security unit may stay where it is, or if it is not in the first city, it may move exactly one city to the left. Every unit can move at most once.

After all moves are chosen, a city is protected if at least one security unit is stationed there. Return the maximum total population of all protected cities.

Function Description

Complete the function maximizeProtectedPopulation in the editor below.

maximizeProtectedPopulation has the following parameters:

  1. int[] population: the city populations
  2. String unit: the initial security-unit layout

Returns

long: the maximum total population of protected cities.

Examples
01 · Example 1
population = [10, 5, 8, 9, 6]
unit = "01101"
return = 27

Move the unit from city 2 to city 1, keep the unit in city 3, and keep the unit in city 5. Cities 1, 3, and 5 are then protected, for a total population of 10 + 8 + 9 = 27.

02 · Example 2
population = [7, 4]
unit = "01"
return = 7

Move the only unit left from city 2 to city 1. Protecting city 1 yields the larger total population.

Constraints
  • population.length = unit.length()
  • unit contains only '0' and '1'
  • Each security unit may move left by at most one city, and may move at most once.
More Amazon problems
drafts saved locally
public long maximizeProtectedPopulation(int[] population, String unit) {
    // write your code here
}
population[10, 5, 8, 9, 6]
unit"01101"
expected27
sign in to submit