会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
题解
题目描述
给定一个由n个正整数构成的数组，我们可以删除恰好一个元素，求删除后数组中前缀最大值的最大数量。前缀最大值定义为：某个元素之前的所有元素都比它小。
思路分析
- 前缀最大值预处理：首先计算原数组中每个位置的前缀最大值数量和当前最大值，以便快速获取删除某个元素后的前缀部分信息。
- 后缀递增子序列预处理：从右到左预处理每个位置的最长递增子序列（LIS）长度，用于快速获取删除元素后剩余数组的递增序列长度。
- 组合求解：对于每个可能的删除位置，计算前缀部分的数量和剩余部分能形成的最长递增子序列长度之和，取最大值作为答案。
P2863.第1题-前缀最大值
题目内容
给定一个由n个正整数构成的数组{a1,a2,....,an}。
如果a中的任意一个元素aj(1≤j≤n),其对于所有的(1≤i≤j−1)，都有ai<aj，则我们称aj为前缀最大值。
现在，你可以从数组中删除恰好一个元素,请问你能够得到的前缀最大值的最大数量是多少?
输入描述
第一行包含一个整数n(1≤n≤105)代表数组中的元素数量。
接下来一行包含n个正整数a1,a2,...,an(1≤ai≤109),表示数组a中的元素。
输出描述
在一行上输出一个整数，代表能够获得的前缀最大值的最大数量
样例1
输入
5
8 3 5 7 6
输出
3
说明
在给定的样例中，我们可以删除数组a中的第一个元素i得到{3,5,7,6}。此时3,5,7均为前缀最大值.
