一、最大子数组和
最大子数组和
算法原理：
💡细节：
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;
}
}
