每天一道算法题12

给定一个数组arr,长度为N,你可以把任意长度大于0且小于N的前缀作为左部分,剩下的作为右部分。
但是每种划分下都有左部分的最大值和右部分的最大值,请返回最大的,左部分最大值减去右部分最大值的绝对值。

解答:这道题咋看很难,其实很骚,哈哈哈。找到整个数组的最大值,然后减去最左边的,和减去最右边的比较,谁大谁就是答案。
因为再怎么分割,无外乎两种情况,一是最大值分割在了左边,那么此时包含了最右边的最大值一定大于等于最右边数。一种是最大值分割
在了右边,那么此时包含了最左边的区域的最大值一定是大于等于最左边数,所以两者分割情况一比较,较大的就是答案

public static int dividerMax(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max,arr[i]);
    }
    return Math.max(max - arr[0], max - arr[arr.length -1]);
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 算法这个活动很严,每天必须打卡,而且不限制语言,群内已有PHP、Python、Java、Javascript...
    鸡汤小弟阅读 386评论 5 4
  • 【荷兰国旗问题】给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间...
    雨打空城阅读 184评论 0 1
  • 【预处理数组-RRRGGG】有一些排成一行的正方形,每个正方形已经被染成红色或者绿色,现在可以选择任意一个正方形然...
    雨打空城阅读 335评论 0 0
  • 【装水】给定一个数组arr, 已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水?比如:ar...
    雨打空城阅读 294评论 0 0
  • 目录 1 时间复杂度 2 树 3 散列 4 优先级队列(堆) 5 排序 6 图参考资料 · 《数据结...
    小小千千阅读 972评论 0 0