#牛客堂直播视频#换标准和算法原型不得不说的故事(9.2)
【本期题目】
题目一
最长的可整合子数组的长度
先给出可整合数组的定义。如果一个数组在排序之后,每相邻两个数差的绝对值都为1,则该数组为可整合数组。例如,[5,3,4,6,2]排序之后为[2,3,4,5,6],符合每相邻两个数差的绝对值都为1,所以这个数组为可整合数组。给定一个整型数组arr,请返回其中最大可整合子数组的长度。例如,[5,5,3,2,6,4,3]中最大可整合子数组为[5,3,2,6,4],所以返回5。
题目二
子数组的最大累加和问题
给定一个数组arr,返回子数组的最大累加和。例如,arr=[1,-2,3,5,-2,6,-1],所有的子数组中,[3,5,-2,6]可以累加出最大的和12,所以返回12。
题目三
找到两个不相容子数组的最大和
给定一个数组arr,其中有很多的子数组,找到两个不相容子数组使得相加的和最大,并返回和的最大值。比如,数组[1,-1,0,-2,3,5,-2,8,7,-4],两个不相容子数组分别为[3,5]和[8,7]时累加和最大,所以返回23。再比如,数组[3,-1,0,-2,3,5,-2,8,7,-4],两个不相容子数组分别为[3]和[3,5,-2,8,7]时累加和最大,所以返回24。
题目四
子矩阵的最大累加和问题
给定一个矩阵matrix,其中的值有正、有负、有0,返回子矩阵的最大累加和。 例如,矩阵matrix为:
-90 48 78
64 -40 64
-81 -7 66
其中,最大累加和的子矩阵为:
48 78
-40 64
-7 66
所以返回累加和209。
再例如,matrix为:
-1 -1 -1
-1 2 2
-1 -1 -1
其中最大累加和的子矩阵为:
2 2
所以返回累加和 4。
题目五
给定一个无序数组arr,其中元素可正、可负、可0,再给定一个整数k,求arr所有的子数组中累加和为k的最长子数组长度。
题目六
给定一个无序数组arr,其中元素可正、可负、可0,求arr所有的子数组中正数与负数个数相等的最长子数组长度。
题目七
给定一个无序数组arr,其中元素只是1或0,求arr所有的子数组中0和1个数相等的最长子数组长度。
【分享嘉宾介绍】
左程云
华中科技大学本科--计算机科学与技术专业、 芝加哥大学硕士--计算机科学专业
IBM软件工程师、 百度软件工程师、 刷题5年的算法热爱者
《程序员代码面试指南--IT名企算法与数据结构题目最优解》 作者,电子工业出版社7月底将出版发行,书籍涉及算法与数据结构编程题目240道以上,并且个人实现出最优解,大部分题目为面试高频题
【参与牛客堂直播】
每周三晚8:00~9:30,直播页面http://www.nowcoder.com/live/courses
【直播题目讨论】
加入牛客3群260877110
【本期答案领取地址】
加入牛客讨论5群(272820159)
群资料中文件:牛课堂2015.9.2代码