Amazon OA：安全单位最多左移一格，最大保护人口

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 人口非负，每个城市初始最多一个单位；城市编号在示例中用0起始。
• 允许不移动，移动无费用，两个单位落同城只计一次保护。

解题路线

1. 找每段连续1，位置[a,b]含L=b-a+1个单位。若a=0无法向左扩张，全部留下覆盖该段；非负人口保证不制造重叠最优。
2. 若a>0，前一城市a-1为0。单位只能覆盖[a-1,b]这L+1城，最多L个不同城市，所以人口和减去最小人口是上界。
3. 这个上界可达：要略过j∈[a-1,b]，把起始位置≤j的单位左移，其余留下。这样恰好覆盖范围中除j外全部城市，且无重叠。
4. 不同连续1段中间至少一个0；前段候选范围止于b，下一段候选从a_next-1≥b+1起，因此互不相交。每段独立取最优后相加。
5. 不要凭单单位局部比较就立即移动：后续单位可以接续覆盖本城，正确选择取决于整段。负人口或单位数量非0/1将改变模型。

手动走一遍

训练population=[10,1,8,7]、units=[0,1,1,0]，候选[10,1,8]略过最小1：第1城单位左移到0，第2城单位留2，总保护18；若两个都左移则只保护11。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximum_protected_population(population, units):
    """One initial unit per 1, may stay or move one position left."""
    if len(population) != len(units) or any(p < 0 for p in population) or any(u not in (0,1) for u in units):
        raise ValueError("invalid population or unit flags")
    answer = 0
    i = 0
    while i < len(units):
        if not units[i]:
            i += 1
            continue
        start = i
        while i < len(units) and units[i]:
            i += 1
        if start == 0:
            answer += sum(population[start:i])
        else:
            candidates = population[start-1:i]
            answer += sum(candidates)-min(candidates)
    return answer

复杂度

O(n)时间；示例切片每段合计O(n)临时量，最大单段O(n)空间。维护sum和min可改成O(1)额外空间。

易错点与追问

容易失分的边界

• 每单位贪心选左右较大，忽略段内相互影响。
• 两个单位同城重复加人口。
• 允许右移或多次左移却沿用证明。

继续深挖

• 允许负人口且可不部署怎么改？
• 最多左移两格还能用段公式？
• 需要输出具体移动方案？