【刷题之路】牛客剑指offer JZ42 连续子数组的最大和

• 一、题目描述
• 二、解题
• • 1、方法1——暴力法
  • • 1.1、思路分析
    • 1.2、代码实现
  • 2、方法2——动态规划
  • • 2.1、思路分析
    • 2.2、代码实现
    • 2.3、改进1
    • 2.4、改进2

一、题目描述

原题连接： JZ42 连续子数组的最大和

题目描述：
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:1<=n<=2×10^5
−100<=a[i]<=100

要求:时间复杂度为O(n)，空间复杂度为O(n)
进阶:时间复杂度为O(n)，空间复杂度为O(1)

示例1
输入：[1,-2,3,10,-4,7,2,-5]
返回值： 18
说明：
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2
输入：[2]
返回值： 2

示例3
输入：[-10]
返回值：-10

二、解题

1、方法1——暴力法

1.1、思路分析

枚举出所有的子数组，求出子数组中元素的总和，每次都跟已有的最大子数组元素总和max_sum进行对比。
枚举完所有的子串后，我们也就求出了连续子数组的最大和。

1.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

int FindGreatestSumOfSubArray1(int* array, int arrayLen) {assert(array);int i = 0;int j = 0;int max_sum = array[0]; // 存储最大的子数组的和，默认初始化为array[0]for (i = 0; i < arrayLen; i++) {int part_sum = 0; // 存储每个子数组的和for (j = i; j < arrayLen; j++) {part_sum += array[j];if (part_sum > max_sum) {max_sum = part_sum;}}}return max_sum;
}

时间复杂度：O(n^2)，其中n为数组元素个数。
空间复杂度：O(1)，我们只需要用到常数级的额外空间。

这个算法的时间复杂度过大，提交给牛客网是不给通过的。

2、方法2——动态规划

2.1、思路分析

我们想想，这道题是不是跟 LeetCode 5.最长回文子串 很类似啊？
所以我们也可以用与那一题一样的动态规划思路：
我们可以设置动态规划表dp，dp[i][j]表示从下标为i的元素到下标为j的元素的子数组中元素的总和，所以状态转移方程为：
dp[i][j] = dp[i + 1][j - 1] + array[i] + array[j]
因为dp对角线上的元素表示的是一个单独的元素，所以我们可以先对
对角线的元素进行初始化。
然后填表时候为了填表的正确性，我们还是要先一列一列地填，再一行一行的填。
且dp[i][j] 和dp[j][i]其实是同一个子数组，所以我们填表就只需要填对角线及其上半部分即可。

2.2、代码实现

有了以上思路，那我们写起代码来也就水到渠成了：

int FindGreatestSumOfSubArray2(int* array, int arrayLen) {assert(array);// 先试用malloc函数模拟出一个二维数组dpint** dp = (int**)malloc(arrayLen * sizeof(int*));int i = 0;for (i = 0; i < arrayLen; i++) {dp[i] = (int*)malloc(arrayLen * sizeof(int));}int max_sum = array[0];// 先初始化对角线for (i = 0; i < arrayLen; i++) {dp[i][i] = array[i];if (dp[i][j] > max_sum) {max_sum = dp[i][j];}}// 再填入其他部分int j = 0;for (j = 1; j < arrayLen; j++) {for (i = 0; i < j; i++) {dp[i][j] = dp[i + 1][j - 1] + array[i] + array[j];if (dp[i][j] > max_sum) {max_sum = dp[i][j];}}}for (i = 0; i < arrayLen; i++) {free(dp[i]);dp[i] = NULL;}free(dp);dp = NULL;return max_sum;
}

时间复杂度：O(n^2)，其中n为数组元素个数。
空间复杂度：O(n^2)，其中n为数组元素个数。

但这个算法的时间和空间的复杂度都过大，提交给牛客网也是不给过的。

2.3、改进1

改进思路：
我们应该想想这一题和那道求最长回文子串的题有什么不同，求回文子串求的是“最长”而我们这题求的是“最大和”。在求最长回文子串的时候当一个子串的长度增加时，只可能有两种情况增长后的字串不是回文串和是回文串，如果是回文串，那么最长回文串的长度就一定会增加。而现在我们求的最大子串总和当子串的长度增加时，总和有可能是减小的，因为在子串增长的时候后面又可能遇到的是负数。
所以我们这提并不需要记录所有子串的总和，我们只需要记录总和比之前的子串的总和更大的总和即可。
所以我们就有了以下思路：
设置一个一维数组dp，dp[i]表示以元素array[i]为结尾的子串中包含的所有子串中最大子串总和。
动态转移方程为：
dp[i] = max(dp[i - 1] + array[i], array[i])。
每求出一个dp[i]，我们都将它与现已有的最大子串总和max_sum进行比较，当我们遍历完数组之后，我们就求出了连续子数组的最大和。

改进代码实现：
有了以上改进思路，那我们再写起代码来也就水到渠成了：

int Max(int x, int y) {return x > y ? x : y;
}
int FindGreatestSumOfSubArray3(int* array, int arrayLen) {assert(array);// 先用malloc函开辟一块空间模拟一维数组dpint* dp = (int*)malloc(arrayLen * sizeof(int));int max_sum = array[0];dp[0] = array[0];int i = 0;for (i = 1; i < arrayLen; i++) {dp[i] = Max(dp[i - 1] + array[i], array[i]);if (dp[i] > max_sum) {max_sum = dp[i];}}free(dp);dp = NULL;return max_sum;
}

时间复杂度：O(n)，其中n为数组元素个数，我们需要遍历一遍数组。
空间复杂度：O(n)，我们需要n个整型空间来存储以元素array[i]为结尾的子串的最大元素总和。

2.4、改进2

改进思路：

既然我们每次求出dp[i]都是为了和max_sum进行对比，也就是说对每个dp[i]的使用都是一次性的，那又何必把每个dp[i]都存起来呢？
我们完全可以只用一个变量来存储以array[i]为结尾的子串的最大元素总和。
改进代码实现：
有了以上改进思路，那我们再写起代码来也就水到渠成了：

int FindGreatestSumOfSubArray4(int* array, int arrayLen) {assert(array);int max_sum = array[0];int dp = array[0];int i = 0;for (i = 1; i < arrayLen; i++) {dp = Max(dp + array[i], array[i]);if (dp > max_sum) {max_sum = dp;}}return max_sum;
}

时间复杂度：O(n)，其中n为数组元素个数，我们只需要遍历一遍数组即可。
空间复杂度：O(1)，我们只需要用到常数级的额外空间。