#622. 最广山脉

    ID: 622 传统题 1000ms 256MiB 尝试: 9 已通过: 3 难度: 2 上传者: 标签>基础算法枚举贪心安徽合肥市经开区区赛2019

最广山脉

题目背景

小美的爸爸特别爱好登山,在小美很小的时候就带着她爬大蜀山、紫蓬山。在小美上小学期间,他们一家还去过天柱山、黄山、华山等等很多名山。图图常听小美聊登山的趣闻,听得心里直痒痒。他常想,要是自己也在小美家,该有多好呀。图图也曾问过小美,她爸爸最想爬的是哪座山,她说可能是珠穆朗玛峰吧,但是太危险,真的太危险了,所以不曾去过。图图对于这些大山,虽身不能至,但心向往之。有时他会在纸上写下他知道的一些山峰的高度,然后他想,如果把这些高度写成一行,就会构成多个起伏多变的地形。当然,总有一些山峰,会连绵成一片广袤的山脉。

题目描述

现有 nn 座山峰,若第 ii 座山峰的高度为 a[i]a[i]。现在给出“最广山脉”的定义:在 xxyy 的范围内(xyx\le y),若存在 kk,满足

$$a[x] < a[x+1] < \dots < a[k-1] < a[k] > a[k+1] > \dots > a[y-1] > a[y], $$

则从 xxyy 构成了一片 山脉(即先严格单调上升到峰值,再严格单调下降)。若在所有满足条件的区间中,某区间包含的数最多,则称该区间为 最广山脉

请你统计并输出给定 nn 个山峰中,最广山脉包含的山峰数量(即最长的“先升后降”的子段长度)。

必须要严格满足先递增后递减,只递增或只递减则不符合题目要求

输入格式

共两行:

  • 11 行:正整数 nn,表示山峰数量。
  • 22 行:nn 个正整数,表示每座山峰的高度 a[1],a[2],,a[n]a[1],a[2],\dots,a[n](以空格分隔)。

输出格式

输出一行:一个正整数,表示最广山脉的山峰数量(即满足先严格上升后严格下降的最长区间的长度)。

样例输入

7
260 1860 100 480 800 650 400

样例输出

5

样例说明

本样例中存在两处山脉:

  • 区间 [1,3][1,3]260,1860,100260,1860,100(长度 33);
  • 区间 [3,7][3,7]100,480,800,650,400100,480,800,650,400(长度 55)。

因此最广山脉长度为 55

数据范围

  • 对于 60%60\% 的数据,1n1041\le n\le 10^4
  • 对于 100%100\% 的数据,1n1061\le n\le 10^6
  • 对于 100%100\% 的数据,1a[i]88481\le a[i]\le 8848