园林修剪

[编程题]园林修剪

热度指数：166 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

园林里有一排共 $n$ 棵树，每棵树的初始高度为 $H[i]$ 。修建要求是：对于任意一棵树，不会有左右两边同时存在比它高的树，且修剪后所有树的高度总和最大。现在想知道修剪后每棵树的高度。

输入描述:

第一行一个整数，表示一排有颗树。
第二行个整数以空格隔开，表示每棵树的初始高度。

输出描述:

一行个整数以空格隔开，表示修剪后每棵树的高度。

示例1

输入

7
1 2 1 2 1 2 1

输出

1 1 1 1 1 2 1

示例2

输入

5
1 2 3 2 1

输出

1 2 3 2 1

备注:

算法知识视频讲解

我讨厌递归算法

发表于 2023-03-14 10:46:30

以最矮的树作为观察点有两种选择 1: 将该树前面所有的树修得和它一样高，然后递归处理后面的树 2：将该树后面所有的树修得和它一样高，然后递归处理前面的树 3: 比较两种选择，选择大的，然后作相应的修理，并且返回大的数据比较大，可能会超出和可能会超出int类型范围，因此使用long，此外不要使用循环展开全文