首页 > 试题广场 >

最大的leftMax与rightMax之差的绝对值

[编程题]最大的leftMax与rightMax之差的绝对值

给定一个长度为N(N>1)的整形数组arr, 可以划分成左右两个部分，左部分为arr[0…K]，右部分为arr[K+1…N-1], K可以取值的范围是[0,N-2]。求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值中，最大是多少

[要求]

时间复杂度为O(n), 空间复杂度为O(n)

第一行一个整数N，表示数组长度。
接下来一行N个整数，表示数组内的数。

输出一个整数表示最优答案

示例1

输入

5
2 7 3 1 1

当左部分为[2, 7]，右部分为[3, 1, 1]时，左部分中的最大值减去右部分的最大值的绝对值为4,。当左部分为[2, 7, 3]，右部分为[1, 1]时，左部分中的最大值减去右部分最大值的绝对值为6。还有很多划分方案，但最终返回6.

算法知识视频讲解

暂无题解

动态规划思维

上传者：小小

难度：

4条回答 9收藏 4613浏览

查看代码

扫一扫，把题目装进口袋