前言
先讲讲我对于这个问题的理解吧
当谈到解决子数组问题时，动态规划(DP)是一个强大的工具，它在处理各种算法挑战时发挥着重要作用。动态规划是一种思想，它通过将问题分解成更小的子问题并以一种递归的方式解决它们，然后利用这些解决方案来构建原始问题的解。在动态规划中，我们经常会遇到两种状态：一种是单独成一段，另一种是以 i 结尾的子数组。
通过枚举和动态规划，我们可以有效地解决子数组问题。枚举法需要考虑所有可能的子数组组合，然后比较它们以找到最优解。这种方法通常需要较多的时间和空间，因为它需要枚举所有可能性。而动态规划则更加智能化，它通过保存历史记录来避免不必要的重复计算。这样，下次遍历时，我们可以利用之前的计算结果，从而大大提高了效率。
动态规划的一个常见技巧是前缀和，它可以帮助我们快速求出数组中任意子数组的和。前缀和的核心思想是将原始数组中每个位置的值累加起来，形成一个新的数组，然后利用这个新数组来快速计算子数组的和。这种方法在处理求子数组和的问题时非常实用，因为它将复杂度降低到了单一状态的动态规划。
另外，预处理也是动态规划中常用的技巧之一。通过将经常使用的数据存储起来，我们可以在需要时快速获取，从而减少计算时间。预处理的思想是在问题出现之前就对数据进行处理，以便在需要时能够迅速获取所需的信息。
综上所述，动态规划是一种强大的解决子数组问题的方法，通过合理利用枚举、动态规划、前缀和和预处理等技巧，我们可以高效地解决各种复杂的算法挑战，为问题提供简单明了的解决方案。
这是我记得笔记
我准备了五道例题都是这些解决方案
1.求最大子数组的和
思路分析:这一题主要是使用动态规划，也可以使用前缀和，动态规划也是求子数组的普遍思路，有两种状态，1自己组成子数组 和 前面的组成子数组，所以状态转移方程也就是Max(nums[i],dp[i - 1] + nums[i])
代码实现
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];//以i位置为结尾的最大子数组和 (多状态 前面i - 1的子数组要 和 不要)
// 初始化 (因为存在负数)
dp[0] = -0x3f3f3f3f;
//前面子数组都是以i - 1位置为结尾 或者 i位置自己构成一个数组
for (int i = 1; i <= nums.length; i++) {
dp[i] = Math.max(nums[i - 1], dp[i - 1] + nums[i - 1]);
}
int max = -0x3f3f3f3f;
for (int i = 0; i < dp.length; i++) {
max = Math.max(dp[i], max);
}
return max;
}2.求最大环形子数组
思路分析:
中间的是连续的所以求内部最小子数组和就好了， 或者中间成最大子数组和 //f[]表示以i位置为结尾的所有子数组中的最大值 //g[]表示以i位置为结尾的所有子数组中的最小值 //g[]就是为了处理边界。他通过计算中间部分的最小值来结算环的最大值
public int maxSubarraySumCircular(int[] nums) {
int sum = 0;//用来处理最小值
int n = nums.length;
//1.状态表示
int[] f = new int[n + 1],g = new int[n + 1];
//2.状态转移方程 自己组成子数组 和 自己加上以 i-1位置结尾 的最大子数组
//3.初始化 = 0 即可
for (int i = 1; i <= n; i++) {
f[i] = Math.max(f[i - 1] + nums[i - 1], nums[i - 1]);
g[i] = Math.min(g[i - 1] + nums[i - 1], nums[i - 1]);
sum += nums[i - 1];
}
int maxF = -0x3f3f3f3f;//统计结果
int minG = 0x3f3f3f3f;//统计结果
//可以和上面统一合并，一个循环就够了
for (int i = 1; i <= n; i++) {
maxF = Math.max(maxF,f[i]);
minG = Math.min(minG,g[i]);
}
//为了防止全是负数返回0，所以sum - minG要和0做判断
//因为 -8 - (-8) = 0;全是负数sum = -8 minG = -8 所以要返回maxF
return Math.max(maxF,sum - minG == 0 ? maxF : sum - minG);
}3.和为k的子数组个数
思路分析:
//解法 动态规划 + hash表 k == pre[i](i位置的前缀和) - pre[j - 1] //此时 [j,i]的子数组为k
public int subarraySum(int[] nums, int k) {
int count = 0;//统计出现了多少次
int n = nums.length;
HashMap < Integer, Integer > hash = new HashMap<>();//当词典使用，存储所有前缀和
hash.put(0,1);//记录0出现了1次，防止前缀和单独构成答案
//1.状态表示 以i位置为结尾的区间和
int[] pre = new int[n + 1];
//2.状态转移方程 pre[i] = pre[i - 1] + nums[i]
//3.初始化 防止j - 1 越界 pre[0] = 0
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + nums[i - 1];//下标映射，因为我的pre[0]是虚拟节点
if (hash.containsKey(pre[i] - k)){
count += hash.get(pre[i] - k);
}
hash.put(pre[i],hash.getOrDefault(pre[i],0) + 1);//键为前缀和的值 ，值为出现的次数
}
return count;
}滚动数组优化形成前缀和
//因为上述我们只使用了，pre[i - 1] 和 pre[i] 这两种状态，所以可以使用滚动数组进行优化，设置两个变量即可
//也就是我们熟知的前缀和
public int subarraySum1(int[] nums, int k) {
int count = 0;//统计出现了多少次
int n = nums.length;
HashMap < Integer, Integer > hash = new HashMap<>();//当词典使用，存储所有前缀和
int pre = 0;
hash.put(0,1);//记录0出现了1次，防止前缀和单独构成答案
for (int i = 0; i < n; i++) {
pre += nums[i];
if (hash.containsKey(pre - k)){
count += hash.get(pre - k);
}
hash.put(pre,hash.getOrDefault(pre,0) + 1);//键为前缀和的值 ，值为出现的次数
}
return count;
}4.乘积为k的最大子数组
思路分析:注释都有明确标注状态表示和转移方程
public int maxProduct(int[] nums) {
int n = nums.length;
//1.定义状态表示
int[] f = new int[n + 1];//以i位置为结尾 所有子数组中 乘积的最大值 遇到正数我要你
int[] g = new int[n + 1];//以i位置为结尾 所有子数组中 乘积的最小值 遇到负数我要你
//2.状态转移方程 遇到正数我要最大值(f[i - 1]) 遇到负数我要最小值(g[i - 1])
//3.初始化 防止i - 1越界但不可保存0，因为初始化的初衷就是保证后续的位置不受影响
f[0] = g[0] = 1;//注意多次赋值是从右往左进行的
int ret = -0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
if (nums[i - 1] > 0){
f[i] = Math.max(f[i - 1] * nums[i - 1],nums[i - 1]);
g[i] = Math.min(g[i - 1] * nums[i - 1],nums[i - 1]);
}else {
f[i] = Math.max(g[i - 1] * nums[i - 1],nums[i - 1]);
g[i] = Math.min(f[i - 1] * nums[i - 1],nums[i - 1]);
}
ret = Math.max(ret,f[i]);
}
return ret;
}5.乘积为正数的最长子数组长度
public int getMaxLen(int[] nums) {
int n = nums.length;
int ret = 0;//统计
//1.状态表示
int[] f = new int[n + 1];//以i位置为结尾中的 所有子数组中的 乘积为正数的最大长度
int[] g = new int[n + 1];//以i位置为结尾中的 所有子数组中的 乘积为负数的最大长度
//2.状态转移方程 f[i]如果i位置为正数为 f[i - 1] + 1 负数 g[i - 1] + 1
// g[i]同理正数g[i - 1] + 1 负数 f[i - 1] + 1
//3.初始化 默认长度为0不影响后续结果
for (int i = 1; i <= n; i++) {
if (nums[i - 1] > 0){
f[i] = f[i - 1] + 1;
//当最后一个元素为正数的时候，并且g[i - 1] = 0表示前面没有负数，所以不可能组成负数
g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
}else if (nums[i - 1] < 0){
//当最后一个元素为负数的时候，并且g[i - 1] = 0表示前面没有负数，所以不可能组成正数
f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
g[i] = f[i - 1] + 1;
}else {//处理为0的情况
f[i] = 0;
g[i] = 0;
}
ret = Math.max(ret,f[i]);
}
return ret;
}总结
当解决子数组问题时，动态规划是一个强大而智能的工具。通过将问题分解成更小的子问题并以递归的方式解决它们，动态规划可以高效地找到原始问题的解。在动态规划中，我们常常会遇到两种状态：一种是单独成一段，另一种是以 i 结尾的子数组。
枚举和动态规划是解决子数组问题的两种主要方法。枚举法需要考虑所有可能的子数组组合，然后比较它们以找到最优解。而动态规划则通过保存历史记录来避免不必要的重复计算，从而提高效率。
在动态规划中，常用的技巧包括前缀和和预处理。前缀和可以帮助我们快速求出数组中任意子数组的和，而预处理则可以在问题出现之前就对数据进行处理，以提高计算效率。
综上所述，动态规划是解决子数组问题的一种强大工具，通过合理利用枚举、动态规划、前缀和和预处理等技巧，我们可以高效地解决各种复杂的算法挑战，为问题提供简单明了的解决方案。