算法题求思路

最大绝对值和

题目描述:

给你一个长度为n的序列A1,A2,...,An。然后构造一个长度为n的序列B1,B2,...,Bn。(1≤i≤n,1≤Bi≤Ai)使∑ni=2|Bi−Bi−1| 的值最大。


输入描述

第一行包含一个整数 n 表示序列的长度。(1 <= n <= 50000) 第二行包含n个整数 分别表示 Ai (1 <= i <= n, 1 <= Ai <= 10000)                           

输出描述

输出最大值

样例输入

5
10
1
10
1
10
样例输出

36
#笔试题目#
全部评论
这道题很简单,只需要先对其进行排序,直接采用快速排序即可。然后计算的时候按照,最小最大剩下的最小、最大。依次...   计算出一个值。 然后再按照最大最小剩下的最大、最小。依次...   计算出另一个值, 比较两个值的大小,大值即为所求。 测试的时候想到了这种思路,但是没有考虑到两种排序。刚刚想通了。 比如4个数 22 14 86 65。 按照最小,最大,。。。计算得到第一个和为179。即B为 14 86 22 65 按照最大,最小,。。。计算得到第二个和为166。即B为 86 14 65 22 故所求为179。 并不需要计算出B的形式,只需要计算出符合B的结果,当然也可以从结果知道B应该是哪种排序了。 关键点在于最大最小值要用两次,但是开头的和结尾的只需要用一次。测试的时候没有码出来,有点可惜,虽然我测试的时候就想到思路了。 注意: 最大最小取值的时候直接从两端取就行。因为经过了快速排序的。但是取值间的最大最小值需要用到两次
点赞 回复 分享
发布于 2021-01-06 02:24

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务