FastPrep
Problem · Array

Maximize Protected City Population

Learn this problem
● MediumAmazon logoAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

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

maximizeProtectedPopulation(population: int[], unit: String) → long

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

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 move the unit from city 5 to city 4. Cities 1, 3, and 4 are then protected, for a total population of 10 + 8 + 9 = 27.

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
checking account