JZ42 连续子数组的最大和 JZ85 连续子数组的最大和(二)

83 阅读 0 评论 55 点赞

我是靠谱客的博主火星上翅膀，最近开发中收集的这篇文章主要介绍JZ42 连续子数组的最大和 JZ85 连续子数组的最大和(二)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

本题可以用动态规划来求解。

动态规划：关键就是记住你之前得到的答案。

解决动态规划问题核心就是找出问题之间的联系并记录答案

动态规划解题模板：
1）拆解问题
2）推导方程
3）记录答案

拆解问题：子数组和的最大值，求和，后一项必然依赖前一项，但因为是求最大值，加了当前项后可能值变大，也可能变小。如果前一项是负值，当前项是正值，那么从当前项开始和最大。所以可以把前一项加上当前项与当前项比较取大值。

方程呼之欲出：dp[i]=Math.max(dp[i-1]+array[i],array[i]);

使用一个int数组来保存过程中产生的每一项答案。

public int FindGreatestSumOfSubArray(int[] array) {
int dp[] = new int[array.length];
Arrays.fill(dp,0);
dp[0]=array[0]
for(int i=1;i<array.length;i++){
dp[i]=Math.max(dp[i-1]+array[i],array[i]);
}
Arrays.sort(dp);
return dp[dp.length-1];
}

int数组默认值本来就是0，boolean数组默认值都是false。所以不用Arrays.fill填充。

使用一个中间变量来记录max,每次与dp[i]比较取大值，不用最后用 Arrays.sort排序，此种的时间复杂度为O(n)

代码优化：

public int FindGreatestSumOfSubArray(int[] array) {
int dp[] = new int[array.length];
dp[0]=array[0];
int max = array[0];
for(int i=1;i<array.length;i++){
dp[i]=Math.max(dp[i-1]+array[i],array[i]);
max=max>dp[i]?max:dp[i];
}
return max;
}

复杂度分析：
时间复杂度：O(N)，遍历数组一次
空间复杂度：O(N)，开启数组存储每一项

根据前面的状态方程可得，我们只需要前一项的值，而不需要所有项的值，所以可以使用中间值来记录。

方程改为：y = Math.max(x + array[i], array[i]);

代码优化:

public int FindGreatestSumOfSubArray(int[] array) {
int y = 0;
int x = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
y = Math.max(x + array[i], array[i]);
max = max > y ? max : y;
x = y;
}
return max;
}

复杂度分析：
时间复杂度：O(N)，遍历数组一次
空间复杂度：O(1)，不涉及额外内存空间

总结：
涉及数据结构：数组
涉及算法：动态规划

动态规划思想强调的是从局部最优解通过一定的策略推得全局最优解，从子问题的答案一步步推出整个问题的答案，并且利用空间换时间。

JZ85 连续子数组的最大和(二)
题目：
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算

解法一：动态规划+滑动窗口

因为不仅仅是要统计最大，还要求出对应的子数组。对于数组求连续的子数组，可以考虑滑动窗口。

使用两个滑动窗口，分别记为临时窗口和结果窗口。

加上当前数后和当前数相比，如果当前数大，说明之前的为负数，不加之前的和更大，所以从当前项重新开始。那么临时左窗口等于临时右窗口。

如果加上当前数大，说明之前的为正数，那么算上之前的和更大。

动态规划方程：dp[i]=Math.max(array[i],dp[i-1]+array[i]);

对于最大和max小于dp[i]或者max=dp[i]且dp[i]对应的数组长度大于max对应的数组长度，则交换max和dp[i]的值，以及临时窗口和结果窗口的值。

返回的时候返回这个结果窗口中对应的原数组的元素。

public int[] FindGreatestSumOfSubArray (int[] array) {
int[] dp = new int[array.length+1];
dp[0]=array[0];
int max=dp[0];
int left=0,right=0;
int resl=0,resr=0;
for(int i=1;i<array.length;i++){
right++;
dp[i]=Math.max(array[i],dp[i-1]+array[i]);
if(array[i]>dp[i-1]+array[i]){
left=right;
}
if(max<dp[i]||(max==dp[i]&&(right-left+1)>(resr-resl+1))){
max=dp[i];
resl=left;
resr=right;
}
}
int[] res= new int[resr-resl+1];
for(int i=0;i<res.length;i++){
res[i]=array[resl++];
}
return res;
}

动态规划优化：因为只用到了前一项，所以可以使用中间值来代替数组存储

public int[] FindGreatestSumOfSubArray (int[] array) {
int left=0,right=0;
int resl=0,resr=0;
int max=array[0],pre=array[0];
int cur=0;
for(int i=1;i<array.length;i++){
right++;
cur=Math.max(array[i],pre+array[i]);
if(array[i]>pre+array[i]){
left=right;
}
if(max<cur||(max==cur&&(resr-resl+1)<(right-left+1))){
max=cur;
resl=left;
resr=right;
}
pre=cur;
}
return Arrays.copyOfRange(array,resl,resr+1);
}