[Algorithm][动态规划][子数组/子串问题][最大子数组和][环形子数组的最大和][乘积最大子数组][乘积为正数的最长子数组长度]详细讲解

本文主要是介绍[Algorithm][动态规划][子数组/子串问题][最大子数组和][环形子数组的最大和][乘积最大子数组][乘积为正数的最长子数组长度]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1.最大子数组和

1.题目链接

• 最大子数组和

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 以i位置元素为结尾的所有子数组中的最大和
      

  • 推导状态转移方程

    • dp[i] = max(nums[i], dp[i - 1] + nums[i])
      

  • 初始化：dp表多开一个虚拟结点，避免处理边界

    • dp[0] = 0

  • 确定填表顺序：从左往右

  • 确定返回值：整个dp表里的最大值

---

3.代码实现

int maxSubArray(vector<int>& nums) 
{int n = nums.size();vector<int> dp(n + 1);dp[0] = 0;int ret = INT_MIN;for(int i = 1; i <= n; i++){dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);ret = max(ret, dp[i]);}return ret;
}

---

2.环形子数组的最大和

1.题目链接

• 环形子数组的最大和

---

2.算法原理详解

• 本题因为有环形数组，问题并不好处理，但是可以将问题转化为最大子数组和

  • 若最大子数组和出现在中间，则与最大子数组和解法无异
  • 若最大子数组和出现在两边，则可以将问题转化为找中间的最小子数组和
  • 两个情况合并，找其中的最大和即可
    

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • f[i]：以i位置元素为结尾的所有子数组中的最大和
    • g[i]：以i位置元素为结尾的所有子数组中的最小和
      

  • 推导状态转移方程

    • f[i] = max(nums[i], f[i - 1] + nums[i])
    • g[i] = min(nums[i], g[i - 1] + nums[i])
      

  • 初始化：dp表多开一个虚拟结点，避免处理边界

    • f[0] = g[0] = 0 -> 确保dp[0]的值，不会影响后面的求和

  • 确定填表顺序：从左往右

  • 确定返回值：sum == gmin ? fmax : max(fmax, sum - gmin)

---

3.代码实现

int maxSubarraySumCircular(vector<int>& nums) 
{int n = nums.size();vector<int> f(n + 1);vector<int> g(n + 1);int fmax = INT_MIN, gmin = INT_MAX, sum = 0;for(int i = 1; i <= n; i++){int x = nums[i - 1];sum += x;f[i] = max(x, x + f[i - 1]);fmax = max(fmax, f[i]);g[i] = min(x, x + g[i - 1]);gmin = min(gmin, g[i]);}return sum == gmin ? fmax : max(fmax, sum - gmin);
}

---

3.乘积最大子数组

1.题目链接

• 乘积最大子数组

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • f[i]：以i位置元素为结尾的所有子数组中的最大乘积
    • g[i]：以i位置元素为结尾的所有子数组中的最小乘积
      

  • 推导状态转移方程

    • f[i] = max(nums[i], f[i - 1] * nums[i]， g[i - 1] * nums[i])
    • g[i] = min(nums[i], f[i - 1] * nums[i]， g[i - 1] * nums[i])
      

  • 初始化：dp表多开一个虚拟结点，避免处理边界

    • f[0] = g[0] = 1 -> 确保dp[0]的值，不会影响后面的乘积

  • 确定填表顺序：从左往右

  • 确定返回值：f表里的最大值

---

3.代码实现

int maxProduct(vector<int>& nums) 
{int n = nums.size();vector<int> f(n + 1), g(n + 1);f[0] = g[0] = 1;int ret = INT_MIN;for(int i = 1; i <= n; i++){f[i] = max(nums[i - 1], max(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));g[i] = min(nums[i - 1], min(f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]));ret = max(ret, f[i]);}return ret;
}

---

4.乘积为正数的最长子数组长度

1.题目链接

• 乘积为正数的最长子数组长度

---

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • f[i]：以i位置元素为结尾的所有子数组中，乘积为正数的最长长度
    • g[i]：以i位置元素为结尾的所有子数组中，乘积为负数的最长长度
      

  • 推导状态转移方程
    

  • 初始化：dp表多开一个虚拟结点，避免处理边界

    • f[0] = g[0] = 0

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：f表里的最大值

---

3.代码实现

int getMaxLen(vector<int>& nums) 
{int n = nums.size();vector<int> f(n + 1), g(n + 1);int ret = INT_MIN;for(int i = 1; i <= n; 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 = max(ret, f[i]);}return ret;
}

这篇关于[Algorithm][动态规划][子数组/子串问题][最大子数组和][环形子数组的最大和][乘积最大子数组][乘积为正数的最长子数组长度]详细讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---