C. Functions again

Codeforces

IDCF789C

Time1000ms

Memory256MB

Difficulty—

data structuresdptwo pointers

English · Original

Chinese · Translation

Formal · Original

Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arriving, they found that citizens are worried about maximum values of the Main Uzhlyandian Function _f_, which is defined as follows: In the above formula, 1 ≤ _l_ < _r_ ≤ _n_ must hold, where _n_ is the size of the Main Uzhlyandian Array _a_, and |_x_| means absolute value of _x_. But the heroes skipped their math lessons in school, so they asked you for help. Help them calculate the maximum value of _f_ among all possible values of _l_ and _r_ for the given array _a_. ## Input The first line contains single integer _n_ (2 ≤ _n_ ≤ 105) — the size of the array _a_. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (-109 ≤ _a__i_ ≤ 109) — the array elements. ## Output Print the only integer — the maximum value of _f_. [samples] ## Note In the first sample case, the optimal value of _f_ is reached on intervals \[1, 2\] and \[2, 5\]. In the second case maximal value of _f_ is reachable only on the whole array.

乌日兰迪亚又发生了什么事……街上爆发了骚乱……著名的乌日兰迪亚超级英雄羊神谢恩和长颈鹿神斯塔斯被召来拯救局势。他们到达后发现，市民们担心的是主乌日兰迪亚函数 #cf_span[f] 的最大值，该函数定义如下：在上述公式中，必须满足 #cf_span[1 ≤ l < r ≤ n]，其中 #cf_span[n] 是主乌日兰迪亚数组 #cf_span[a] 的大小，而 #cf_span[|x|] 表示 #cf_span[x] 的绝对值。但这些英雄在学校时逃掉了数学课，于是他们向你求助。请帮助他们计算在给定数组 #cf_span[a] 的所有可能的 #cf_span[l] 和 #cf_span[r] 取值中，#cf_span[f] 的最大值。第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 数组 #cf_span[a] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (-#cf_span[109 ≤ ai ≤ 109]) —— 数组元素。请输出一个整数 —— #cf_span[f] 的最大值。在第一个样例中，#cf_span[f] 的最优值在区间 #cf_span[[1, 2]] 和 #cf_span[[2, 5]] 上取得。在第二个样例中，#cf_span[f] 的最大值仅在整个数组上可达。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105]) —— 数组 #cf_span[a] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (-#cf_span[109 ≤ ai ≤ 109]) —— 数组元素。 ## Output 请输出一个整数 —— #cf_span[f] 的最大值。 [samples] ## Note 在第一个样例中，#cf_span[f] 的最优值在区间 #cf_span[[1, 2]] 和 #cf_span[[2, 5]] 上取得。在第二个样例中，#cf_span[f] 的最大值仅在整个数组上可达。

**Definitions** * Let $n \in \mathbb{Z}$ such that $2 \le n \le 10^5$. * Let $A = (a_1, a_2, \dots, a_n)$ be a sequence of integers, where $a_i \in \mathbb{Z}$ and $-10^9 \le a_i \le 10^9$ for all $1 \le i \le n$. * Let $S$ be the set of valid index pairs defined as: $$S = \{ (l, r) \in \mathbb{Z}^2 \mid 1 \le l < r \le n \}$$ **Function Definition** Define the function $f: S \to \mathbb{Z}_{\ge 0}$ as: $$f(l, r) = |a_l - a_r|$$ *(Note: Deduced from the context of interval endpoints and absolute value constraints).* **Objective** Calculate the maximum value of $f$ over the domain $S$: $$ \text{Maximize } f(l, r) \quad \text{subject to} \quad (l, r) \in S $$ Which is equivalent to finding: $$ \max_{1 \le l < r \le n} |a_l - a_r| $$

Samples

Input #1

5
1 4 2 3 1

Output #1

Input #2

4
1 5 4 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Functions again",
    "description": {
      "content": "Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arr",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF789C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Something happened in Uzhlyandia again... There are riots on the streets... Famous Uzhlyandian superheroes Shean the Sheep and Stas the Giraffe were called in order to save the situation. Upon the arr...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "乌日兰迪亚又发生了什么事……街上爆发了骚乱……著名的乌日兰迪亚超级英雄羊神谢恩和长颈鹿神斯塔斯被召来拯救局势。他们到达后发现，市民们担心的是主乌日兰迪亚函数 #cf_span[f] 的最大值，该函数定义如下：\n\n在上述公式中，必须满足 #cf_span[1 ≤ l < r ≤ n]，其中 #cf_span[n] 是主乌日兰迪亚数组 #cf_span[a] 的大小，而 #cf_span[|x|] 表...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**\n\n*   Let $n \\in \\mathbb{Z}$ such that $2 \\le n \\le 10^5$.\n*   Let $A = (a_1, a_2, \\dots, a_n)$ be a sequence of integers, where $a_i \\in \\mathbb{Z}$ and $-10^9 \\le a_i \\le 10^9$ for al...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments