#CW57. 掐头去尾(trim)

掐头去尾(trim)

题目描述

给定一个长度为 nn 的数组 a=(a1,a2,…,an)a=(a_1,a_2,\dots,a_n)。数组中的元素按照下标从左到右排列,删除元素后,剩余元素会自动靠拢,仍然组成一个数组。

对于每个 k=1,2,…,nk=1,2,\dots,n,都要从最初的数组 aa 重新开始一个独立的过程。在这个过程中必须恰好进行 kk 次操作,并且每次操作只能选择下面两种方式之一:

  • Backspace:删除当前数组最左端的元素;
  • Delete:删除当前数组最右端的元素。

一次操作只删除一个元素。进行第 kk 次操作之前,数组中一定还剩下至少一个元素;第 kk 次操作删除的元素就是本次过程的得分,前 k−1k-1 次操作删除的元素不计入得分。对每个 kk,请在所有合法的操作顺序中取最大得分。

每个 kk 的过程互不影响。例如求 k=2k=2 的答案时,不需要沿用求 k=1k=1 时的删除结果,而是再次从完整数组开始。

输入格式

从 trim.in 文件读入数据。

第一行包含整数 nn。第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

将结果输出到 trim.out 文件。

输出 nn 个整数,第 kk 个整数表示恰好操作 kk 次时的最大得分。

样例 1 输入

5
2 7 8 1 4

样例 1 输出

4 7 8 8 8

样例 1 解释

  • k=1k=1 时,只能删除 22 或 44,答案是 44;
  • k=3k=3 时,连续三次选择 Backspace,删除顺序为 2,7,82,7,8,第三次得分为 88;
  • k=4k=4 时,可以先从左侧删除 2,72,7,再从右侧删除 44,最后从左侧删除 88,最后一次仍然可以删除值为 88 的元素。

数据范围

对于全部数据,保证 1≤n≤1051\le n\le 10^5,且 1≤ai≤1091\le a_i\le 10^9。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5 n≤100n\le 100
2 6∼106\sim 10 n≤1000n\le 1000
3 11∼1511\sim 15 n≤104n\le 10^4
4 16∼2016\sim 20 n≤105n\le 10^5