1000ms

Difficulty: 5

所属公司 : 美团

时间 :2024年3月30日

算法与标签>前缀和

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

思路：前后缀分解

对于位置 $i$ 而言， $g(i)$ 由以下三个部分组成

题目内容

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$ 。对于每个位置 $i$ （ $1 \le i \le n$ ），定义 $g(i)$ 为：将 $a_i$ 替换为它的两倍（即 $2 imes a_i$ ）后，整个序列的最大值。

请你求出 $g(1)$ 到 $g(n)$ 的所有值。

约束条件：

序列的长度 $n$ 不超过 $2 imes 10^5$ 。
序列中的每个元素 $a_i$ 均为正整数，且不超过 $10^9$ 。