問題一覧 > ネタ問題

No.3103 Range Chmax and Maximize Abs Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : first_vilfirst_vil / テスター : milkcoffeemilkcoffee
0 ProblemId : 8439 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-12 12:55:07

問題文

テーブルの上に $N$ 個の整数が左右一列に並んでいます。 あなたはこれから以下の操作を $0$ 回以上の好きな回数行います。

  • 整数 $l,r\ (1 \le l \le r \le N)$ を選ぶ。テーブルの左から $l,l+1,\dots,r$ 番目の整数を全てそれらの最大値に置き換える。

操作後の各整数の絶対値の総和としてあり得る最大値を求めてください。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

$1$ 行目にはテーブルの上に並んでいる整数の個数 $N$ が与えられる。$N$ は $1 \le N \le 200000$ を満たす。

$2$ 行目にはテーブルの上に並んでいる $N$ 個の整数 $A_1,A_2,\dots,A_N$ が半角空白で区切られて与えられる。各 $A_i$ は $-1000000000 \le A_i \le 1000000000$ を満たす。

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
2 -2 1 -3
出力
9

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。