#牛客堂直播视频#换标准和算法原型不得不说的故事（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代码
小天才公司福利 1160人发布
查看9道真题和解析