前言
众所周知,《剑指offer》是一本“好书”。
如果你是个算法菜鸡(和我一样),那么最推荐的是先把剑指offer的题目搞明白。
对于剑指offer题解这个系列,我的写作思路是,对于看过文章的读者,能够做到:
- 迅速了解该题常见解答思路(偏门思路不包括在内,节省大家时间,实在有研究需求的人可以查阅其它资料)
- 思路尽量贴近原书(例如书中提到的面试官经常会要求不改变原数组,或者有空间限制等,尽量体现在代码中,保证读者可以不漏掉书中细节)
- 尽量精简话语,避免冗长解释
- 给出代码可运行,注释齐全,关注细节问题
《剑指offer题解》系列
你可以通过以下两种途径查看《剑指offer题解》系列:
- 关注我的公众号:Rude3Knife,点击公众号下方:剑指offer题解专栏
- 剑指offer题解专栏(CSDN)
题目介绍
由 N 个整数元素(有正数也有负数)组成的一维数组 (A[0], A[1],…,A[n-1], A[n]),这个数组有很多连续子数组,那么其中数组之和的最大值是什么呢?
子数组必须是连续的。
要求时间复杂度O(n)
解题思路
方法一:暴力枚举子数组
思路
一个长度为n的数组,共有n(n+1)/2个子数组,计算出所有子数组的和,最快需要O(n^2)的时间复杂度,虽然完成了计算,但是时间复杂度不符合。
方法二:找规律
思路
思路如原书给出的如下表格,主要思想是:
- 记录两个数,最大的子数组和+累加子数组和
- 遍历数组,随时更新最大的子数组和
- 一旦累加数为负数,直接放弃,将累加子数组和设置为0
代码
1 | public int FindGreatestSumOfSubArray(int[] array) { |
方法三:动态规划
思路
如果你还不熟悉动态规划,先去了解下动态规划吧~
也可以戳这里看我的动态规划算法题总结:
https://blog.csdn.net/qqxx6661/article/details/79951989
回到这题,动态规划表达式是:
1 | dp[i] = dp[i-1] + s[i] (dp[i-1] >= 0) |
可以从下表看出这题的规律:
1 | list -2 1 -3 4 -1 2 1 -5 4 |
代码
1 | public int FindGreatestSumOfSubArray_2(int[] array) { |
总结
这题方法二和方法三其实异曲同工啦,是一道比较简单的题~
拓展问题
最大子矩阵问题
给定一个矩阵(二维数组),其中数据有大有小,请找一个子矩阵,使得子矩阵的和最大,并输出这个和。
思路:
原始矩阵可以是二维的。假设原始矩阵是一个3 * n 的矩阵,那么它的子矩阵可以是 1 * k, 2 * k, 3 * k,(1 <= k <= n)。 如果是1*K,这里有3种情况:子矩阵在第一行,子矩阵在第二行,子矩阵在第三行。如果是 2 * k,这里有两种情况,子矩阵在第一、二行,子矩阵在第二、三行。如果是3 * k,只有一种情况。
为了能够找出最大的子矩阵,我们需要考虑所有的情况。假设这个子矩阵是 2 * k, 也就是说它只有两行,要找出最大子矩阵,我们要从左到右不断的遍历才能找出在这种情况下的最大子矩阵。如果我们把这两行上下相加,情况就和求“最大子段和问题” 又是一样的了。
《剑指offer题解》系列
你可以通过以下两种途径查看《剑指offer题解》系列:
- 关注我的公众号:Rude3Knife,点击公众号下方:剑指offer题解专栏
- 剑指offer题解专栏(CSDN)
关注我
我是一名后端开发。主要关注后端开发,数据安全,爬虫等方向。微信:yangzd1102
Github:@qqxx6661
个人博客:
原创博客主要内容
- Java知识点复习全手册
- Leetcode算法题解析
- 剑指offer算法题解析
- SpringCloud菜鸟入门实战系列
- SpringBoot菜鸟入门实战系列
- Python爬虫相关技术文章
- 后端开发相关技术文章
个人公众号:Rude3Knife
如果文章对你有帮助,不妨收藏起来并转发给您的朋友们~