Ալգորիթմներ և Տվյալների Կառուցվածքներ

Հիստոգրամի ամենամեծ ուղղանկյուն մակերեսը

Ձեզ տրված են n թվեր, որոնք ցույց են տալիս հիստոգրամի սյուների բարձրությունները։ Պահանջվում է հաշվել այն առավելագույն մակերեսը, որը հնարավոր է ստանալ հիստոգրամի ներսում՝ առանց դուրս գալու սյուների սահմաններից:

Հիստոգրամի բոլոր սյուները ունեն 1 լայնություն, իսկ դրանց բարձրությունները կամայական ոչ բացասական ամբողջ թվեր են:

6.png

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ ):

Հաջորդ տողում տրված են n բացատով բաժանված թվեր a_1, a_2, ..., a_n (0 ≤ ≤ ):

Ելք

Ծրագիրը պետք է տպի այն առավելագույն մակերեսը, որը հնարավոր է ստանալ հիստոգրամի սյուներից:

Օրինակներ

Մուտք

Ելք

8
6 2 5 4 5 1 6 1

12

Հուշում

Հիստոգրամի յուրաքանչյուր տարրի համար կարելի է հաշվել 2 արժեք՝ ձախ կողմում գտնվող ամենամոտ տարրն, որը փոքր է տվյալ տարրից, և աջ կողմում գտնվող ամենամոտ տարրն, որը նույնպես փոքր է տվյալ տարրից։ Այդ երկու արժեքները հերիք են հաշվելու այն ուղղանկյույթի մակերեսը, որի բարձրությունը հավասար է տվյալ սյան բարձրությանը:

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue