一、最大子数组和
最大子数组和
算法原理:
????细节:
1.返回值为dp表每个位置的最大值,而不是只看最后一个位置,因为可能最后一个位置都不选
2.可以直接在填dp表的时候就进行返回值的比较
3.如果初始化选择多开一个位置,那么就需要注意下标的映射
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];//dp表示以i位置为结尾的所有子数组中的最大和
int ret = Integer.MIN_VALUE;
for(int i=1;i<n+1;i++) {
dp[i] = Math.max(nums[i-1],dp[i-1]+nums[i-1]);//注意下标映射
ret = Math.max(ret,dp[i]);
}
return ret;
}
}
二、环形子数组的最大和
918. 环形子数组的最大和
算法原理
????细节:
1.因为是环形的,我们就跟上次打家劫舍II一样的思路,进行拆分分类讨论,分为(1)结果就在数组中间,跟上题一样,(2)结果在两边,这个时候求最大,那么反向思考,就考虑中间区间最小,进一步转化为(1)
2.返回值:注意当nums数组中元素全为负数时,那么sum-gmin为0,而根据题意,此时的返回值只能为负数,那么就需要特殊考虑这种情况
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];//结果在中间:求以i位置为结果的所有子数组的最大值
int[] g = new int[n+1];//结果在两边:求以i位置为结果的所有子数组的最小值
int fmax = Integer.MIN_VALUE;
int gmin = Integer.MAX_VALUE;
int sum = 0;
for(int i=1;i<n+1;i++) {
int x = nums[i-1];
sum += x;
f[i] = Math.max(x,f[i-1]+x);
fmax = Math.max(fmax,f[i]);
g[i] = Math.min(x,g[i-1]+x);
gmin = Math.min(gmin,g[i]);
}
return sum==gmin?fmax:Math.max(fmax,sum-gmin);
}
}
三、乘积最大子数组
152. 乘积最大子数组
算法原理
????细节:
1.如果只用一个f表时,在分类讨论的时候会发现当nums[i]为负数的时候,f[i-1]*nums[i]也为负,那么就不可能是最大乘积,所以还需要一个g表来表示最小乘积,同时填g表的时候跟f表一样的考虑(考虑nums[i]是正负+长度为1三种情况)
2.初始化的时候注意是乘法,f[0]和g[0]都应该初始化为1
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];//以i位置为结果的所有子数组的最大乘积
int[] g = new int[n+1];//以i位置为结果的所有子数组的最小乘积
f[0] = g[0] = 1;
int ret = Integer.MIN_VALUE;
for(int i=1;i<n+1;i++) {
int x = nums[i-1],y = f[i-1]*nums[i-1],z = g[i-1]*nums[i-1] ;
f[i] = Math.max(x,Math.max(y,z));
g[i] = Math.min(x,Math.min(y,z));
ret = Math.max(ret,f[i]);
}
return ret;
}
}
四、乘积为正数的最长子数组长度
1567. 乘积为正数的最长子数组长度
算法原理
????细节:
1.本题跟上题一样,一个f表无法解决问题,需要一个g表来辅助
2.(1)在分析f表的状态方程时,长度大于1且nums[i]<0的情况下:要判断g[i-1](即最长的负数乘积长度)是否存在的情况,不存在就为0,存在才是g[i-1]+1;在分析g表的状态方程时,长度大于1且nums[i]>0的情况同理
(2)分析完f表和g表可以进行合并,直接分为nums[i]大于0和小于0的情况即可
3.初始化:根据上面的状态表示f[0]和g[0]全部初始化为0即可
class Solution {
public int getMaxLen(int[] nums) {
int n = nums.length;
int[] f = new int[n+1];
int[] g = new int[n+1];
int ret = Integer.MIN_VALUE;
for(int i=1;i<n+1;i++) {
if(nums[i-1]>0) {
f[i] = f[i-1] + 1;
g[i] = g[i-1]==0?0:g[i-1]+1;
}
else if(nums[i-1]<0) {
f[i] = g[i-1]==0?0:g[i-1]+1;
g[i] = f[i-1] + 1;
}
ret = Math.max(ret,f[i]);
}
return ret;
}
}