11270: 【原1270】盾盾吃果果

题目

题目描述

author: Cheezer 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1270

Description

盾盾最喜欢吃果果了。今天，盾盾妈给他带来了一大袋果果，他准备全部吃完。他把每个果果从1~n编号，每个果果有一个喜爱程度ai，但是盾盾特别喜欢刺激，也就是如果先吃到一个不喜欢的果果，再吃一个喜欢的果果，他就会非常高兴。现在可以用一个值F表示盾盾的高兴程度。盾盾要求在给定n个果果及每一个果果的喜欢程度ai的条件下，求一个这些果果的排列bi (n个元素，1<=bi<=n,且对于i<>j,bi<>bj)，使得我们定义的函数 \( F=∑_{j=2}^n max⁡(a[b[j]]-a[b[j-1]],0) \) 最大。请你求出这个最大值。

Input Format

输入包括n+1行。

第一行为n，接下来1行为n个数ai，用空格分开。

100%: N<=100000，Ai<=10^9，F在int范围内

Output Format

一个数，表示最大的函数值F。

Sample Input

5
5 9 3 5 4

Sample Output

7

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！