题目内容

给定一个由n个正整数构成的数组{$a_1,a_2,....,a_n$}。

如果$a$中的任意一个元素$a_j(1≤j≤n)$,其对于所有的$(1≤i≤j-1)$，都有$a_i<a_j$，则我们称$a_j$为前缀最大值。

题解

题目描述

给定一个由n个正整数构成的数组，我们可以删除恰好一个元素，求删除后数组中前缀最大值的最大数量。前缀最大值定义为：某个元素之前的所有元素都比它小。

思路分析

1. 前缀最大值预处理：首先计算原数组中每个位置的前缀最大值数量和当前最大值，以便快速获取删除某个元素后的前缀部分信息。
2. 后缀递增子序列预处理：从右到左预处理每个位置的最长递增子序列（LIS）长度，用于快速获取删除元素后剩余数组的递增序列长度。
3. 组合求解：对于每个可能的删除位置，计算前缀部分的数量和剩余部分能形成的最长递增子序列长度之和，取最大值作为答案。