[剑指offer题解][Java]连续子数组的最大和

悠悠 2021-11-16 08:26 264阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxeHg2NjYx_size_16_color_FFFFFF_t_70]

# 前言 #

众所周知，《剑指offer》是一本“好书”。

如果你是个算法菜鸡（和我一样），那么最推荐的是先把剑指offer的题目搞明白。

对于剑指offer题解这个系列，我的写作思路是，对于看过文章的读者，能够做到：

*  迅速了解该题常见解答思路（偏门思路不包括在内，节省大家时间，实在有研究需求的人可以查阅其它资料）
 *  思路尽量贴近原书（例如书中提到的面试官经常会要求不改变原数组，或者有空间限制等，尽量体现在代码中，保证读者可以不漏掉书中细节）
 *  尽量精简话语，避免冗长解释
 *  给出代码可运行，注释齐全，关注细节问题

## 《剑指offer题解》系列 ##

你可以通过以下两种途径查看《剑指offer题解》系列：

*  关注我的公众号：Rude3Knife，点击公众号下方：剑指offer题解专栏
 *  [剑指offer题解专栏(CSDN)][offer_CSDN]

# 题目介绍 #

由 N 个整数元素（有正数也有负数）组成的一维数组 (A\[0\], A\[1\],…,A\[n-1\], A\[n\])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？

子数组必须是连续的。

要求时间复杂度O(n)

# 解题思路 #

## 方法一:暴力枚举子数组 ##

### 思路 ###

一个长度为n的数组，共有n(n+1)/2个子数组，计算出所有子数组的和，最快需要O(n^2)的时间复杂度，虽然完成了计算，但是时间复杂度不符合。

## 方法二：找规律 ##

### 思路 ###

思路如原书给出的如下表格，主要思想是：

*  记录两个数，最大的子数组和+累加子数组和
 *  遍历数组，随时更新最大的子数组和
 *  一旦累加数为负数，直接放弃，将累加子数组和设置为0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxeHg2NjYx_size_16_color_FFFFFF_t_70 1]

### 代码 ###

public int FindGreatestSumOfSubArray(int[] array) {
    
            if (array.length == 0) {
                return 0;
            }
            
            int maxSum = Integer.MIN_VALUE;
            int curSum = 0;
    
            for (int i = 0; i < array.length; i++) {
                if (curSum <= 0) {
                    curSum = array[i];
                } else {
                    curSum += array[i];
                }
    
                if (curSum > maxSum) {
                    maxSum = curSum;
                }
            }
            return maxSum;
        }

## 方法三：动态规划 ##

### 思路 ###

如果你还不熟悉动态规划，先去了解下动态规划吧~

也可以戳这里看我的动态规划算法题总结：

[https://blog.csdn.net/qqxx6661/article/details/79951989][https_blog.csdn.net_qqxx6661_article_details_79951989]

回到这题，动态规划表达式是：

dp[i] = dp[i-1] + s[i] (dp[i-1] >= 0)
    dp[i] = s[i] (dp[i-1] < 0)

可以从下表看出这题的规律：

list    -2 1 -3 4 -1 2 1 -5 4
    current -2 1  0 4  3 5 6 1  5
    m       -2 1  1 4  4 5 6 6  6

### 代码 ###

public int FindGreatestSumOfSubArray_2(int[] array) {
    
            if (array.length == 0) {
                return 0;
            }
    
            // 新建动态规划数组
            int[] dp = new int[array.length+1];
            // 由于下方遍历从1开始，先写入第一个数进dp[0]
            dp[0] = array[0];
    
            // 设置最大值：由于最开始的是array[0]，后面如果是负数肯定更小，如果是整数肯定变大
            int maxSum = array[0];
    
            for (int i = 1; i < dp.length; i++) {
    
                dp[i] = Math.max(array[i], array[i]+dp[i-1]);
    
                if (dp[i] > maxSum) {
                    maxSum = dp[i];
                }
            }
            return maxSum;
        }

# 总结 #

这题方法二和方法三其实异曲同工啦，是一道比较简单的题~

## 拓展问题 ##

**最大子矩阵问题**

给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。

思路：

原始矩阵可以是二维的。假设原始矩阵是一个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)][offer_CSDN]

# 关注我 #

我是一名后端开发。主要关注后端开发，数据安全，爬虫等方向。微信：yangzd1102

Github：[@qqxx6661][qqxx6661]

个人博客：

*  CSDN：[@qqxx6661][qqxx6661 1]
 *  知乎：[@Zhendong][Zhendong]
 *  简书：[@蛮三刀把刀][Link 1]
 *  掘金：[@蛮三刀把刀][Link 2]

### 原创博客主要内容 ###

*  Java知识点复习全手册
 *  Leetcode算法题解析
 *  剑指offer算法题解析
 *  SpringCloud菜鸟入门实战系列
 *  SpringBoot菜鸟入门实战系列
 *  Python爬虫相关技术文章
 *  后端开发相关技术文章

### 个人公众号：Rude3Knife ###

![个人公众号：Rude3Knife][Rude3Knife]

**如果文章对你有帮助，不妨收藏起来并转发给您的朋友们~**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxeHg2NjYx_size_16_color_FFFFFF_t_70]: /images/20211116/dd972e108c764f3da12f5539d3c3bdd3.png
[offer_CSDN]: https://blog.csdn.net/qqxx6661/column/info/37267
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxeHg2NjYx_size_16_color_FFFFFF_t_70 1]: /images/20211116/0e10147b2f98492597ca985b2c20dda9.png
[https_blog.csdn.net_qqxx6661_article_details_79951989]: https://blog.csdn.net/qqxx6661/article/details/79951989
[qqxx6661]: https://github.com/qqxx6661
[qqxx6661 1]: http://blog.csdn.net/qqxx6661
[Zhendong]: https://www.zhihu.com/people/yang-zhen-dong-1/
[Link 1]: https://www.jianshu.com/u/b5f225ca2376
[Link 2]: https://juejin.im/user/5b48015ce51d45191462ba55
[Rude3Knife]: /images/20211116/b3702df3029a4861ae1989cfb4f9fbb9.png