上海市计算机学会竞赛平台2020年5月丙组最大回撤

题目背景概述

在金融交易市场中，统计某只股票的最大回撤值是一项常见需求。最大回撤具体指投资者于某一交易日购入股票后，在后续交易日卖出时可能遭遇的最严重损失程度，这一指标能够有效体现该股票在过往历史中的最差表现情况。

题目描述

对于一个整数序列 𝑎1,𝑎2,𝑎3,⋯ ,𝑎𝑛a1,a2,a3,⋯,an，其中每一个 𝑎𝑖ai 都代表同一只股票在特定日期的交易价格，需要计算该股票的最大回撤幅度。具体而言，需找到两个满足条件 1≤𝑖≤𝑗≤𝑛1≤i≤j≤n 的下标，并使得 𝑎𝑖−𝑎𝑗ai−aj 的差值达到最大。

输入格式

第一行给出一个单独的整数 𝑛n，
第二行包含 𝑛n 个整数，依次为 𝑎1,𝑎2,𝑎3,⋯ ,𝑎𝑛a1,a2,a3,⋯,an。

输出格式

单个整数：用于体现该股票可能出现的最大跌幅数值，当股价持续上升时，输出结果为 0。

数据范围

• 针对 30% 的数据集，其规模 𝑛 不超过 1000；
  • 针对 60% 的数据集，其规模 𝑛 不超过 10000；
  • 针对 100% 的数据集，其规模 𝑛 范围为 1 至 100000，同时每个数据点 𝑎𝑖 的取值范围限定在 −100000 至 100000。

样例数据展示

输入:

5