devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划算法专题四--子数组系列问题

作者：小惠珠哦 | 2024-07-17 00:30:51

赞

踩

动态规划算法专题四--子数组系列问题

目录

题十八 最大子数组和

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

 题十九 环形子数组的最大和

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

 题二十 乘积最大子数组

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

  题二十一 乘积为正数的最大子数组长度

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

  题二十二 等差数列划分

1、算法解析

1、确定状态：

2、状态转移方程：

3、初始化：

4、填表顺序：

5、返回值：

2、代码

  题二十三 最长瑞流子数组

  题二十四 单词拆分

  题二十五 环绕字符串中唯一的字串

题十八 最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

1、算法解析

1、确定状态：

dp[i]位置的值，表示以i为结尾的子数组的最大和。注意，是以i为结尾，并没有规定从那个位置开始。

2、状态转移方程：

i位置有两种状态：长度为1，长度大于1。
长度为1时，以i结尾，就是i位置的值，即nums[i]
长度大于1时，以i结尾，就是要包括前面i-1位置的和，即dp[i-1] + nums[i]

3、初始化：

初始化解决的是填表越界的问题
根据状态转移方程，我们需要初始化dp[0]的位置
第一个，因为必须包含一个元素，所以只能是其本身值
即dp[0] = n[0]

4、填表顺序：

从左往右

5、返回值：

我们不知道最大值到底是以那个位置为结尾的连续子数组，因此要遍历拿出最大值。

2、代码

  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         //1、创建dp表
  5.         int n = nums.size();
  6.         if(n==1) return nums[0];
  7.         vector<int> dp(n);
  8.  
  9.         //2、初始化
  10.         dp[0] = nums[0];
  11.  
  12.         //3、填表
  13.         for(int i = 1; i<n; ++i)
  14.         {
  15.             dp[i] = max(nums[i], dp[i-1] + nums[i]);
  16.         }
  17.  
  18.         //4、返回值
  19.         int ret = -0x3f3f3f3f;
  20.         for(int i = 0; i<n; ++i)
  21.         {
  22.             if(dp[i] >= ret)
  23.             {
  24.                 ret = dp[i];
  25.             }
  26.         }
  27.         return ret;
  28.  
  29.     }
  30. };

 题十九 环形子数组的最大和

918. 环形子数组的最大和 - 力扣（LeetCode）

1、算法解析

这一题比简单的线性最大数组和多了一个环形。
我们怎么做呢？
可以不可以把环形，变成线性的数组？
如果转化为线性的数组，那就是最大连续子数组和
我们仔细研究一下这个环形，会发现：答案就只有两种可能
一个是最大连续字数组就在中间位置：
一个是最大连续子数组在两边连接处：

这第二种情况，我们会发现中间的连续子数组是最小的。
那么数组的最大值就是整个数组的和-最小连续子数组。
那么，我们就来比较这两种情况那个大即可。

1、确定状态：

我们需要两个表，一个f求最小值，一个g求最大值：
f[i]位置的值，表示以i为结尾的最小连续子数组和。注意，是以i为结尾，并没有规定从那个位置开始。
g[i]位置的值，表示以i为结尾的最大连续子数组和。注意，是以i为结尾，并没有规定从那个位置开始。

2、状态转移方程：

i位置有两种状态：长度为1，长度大于1。
长度为1时，以i结尾，就是i位置的值，即nums[i]
长度大于1时，以i结尾，就是要包括前面i-1位置的和，即f[i-1] + nums[i]

f[i] = min(nums[i], f[i-1] + nums[i]);
g[i] = max(nums[i], g[i-1]  + nums[i]);
一个求最大，一个求最小。

3、初始化：

初始化解决的是填表越界的问题
根据状态转移方程，我们需要初始化f[0]的位置
f[0] = nums[0]
g[0] = nums[0]

4、填表顺序：

从左往右

5、返回值：

找出最大值，和sum-最小值对比，返回大者。
但是，需要注意，如果所有的数组都是负数，最小值就是所有数字的和。
sum - min = 0；就会返回0
但是返回值不能是0，因为必须包含一个元素。
所以需要特别判断

2、代码
 

  1. class Solution {
  2. public:
  3.     int maxSubarraySumCircular(vector<int>& nums) {
  4.         //1、创建dp表
  5.         int n = nums.size();
  6.         if(n == 1) return nums[0];
  7.         vector<int> f(n);
  8.         auto g = f; 
  9.  
  10.         int sum = 0;
  11.         for(auto e : nums)
  12.         {
  13.             sum += e;
  14.         }
  15.  
  16.         //2、初始化
  17.         f[0] = nums[0];
  18.         g[0] = nums[0];
  19.  
  20.         //3、填表
  21.         for(int i = 1; i<n; ++i)
  22.         {
  23.             f[i] = min(nums[i], f[i-1] + nums[i]);//找最小值
  24.             g[i] = max(nums[i], g[i-1] + nums[i]);//找最大值
  25.         }
  26.  
  27.         //4、返回值
  28.         int max_value  = -0x3f3f3f3f;
  29.         int min_value = 0x3f3f3f3f;
  30.         for(int i= 0; i<n; ++i)
  31.         {
  32.             if(g[i] >= max_value)
  33.                 max_value = g[i];
  34.             if(f[i] <= min_value)
  35.                 min_value = f[i];
  36.         }
  37.         
  38.         if(sum == min_value)
  39.             return max_value;
  40.         
  41.         return max(max_value, sum - min_value);
  42.  
  43.  
  44.     }
  45. };

 题二十 乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode）

1、算法解析

1、确定状态：

也是一个连续子数组求最大最小的问题。
我们创建一个一维dp表。
dp[i]的值，表示以i为结尾的最大乘积子数组，注意，并没有规定是从那个位置作为开始位置。

2、状态转移方程：

i位置有两种状态：长度为1，长度大于1。
长度为1时，以i结尾，就是i位置的值，即nums[i]
长度大于1时，以i结尾，就是要包括前面i-1位置的和，即dp[i-1] * nums[i]

按照原来的逻辑，上述的推导是没有问题的。
但是，如果nums[i]是一个负数，dp[i-1]是一个最大值，那么最大值×负数，直接变成最小值。
出问题了。
正确的逻辑应该是：
如果nums[i]是一个正数，那么dp[i-1]的值，应该是最大值
如果nums[i]是一个负数，那么dp[i-1]的值，应该是最小值。
所以，按照我们的逻辑推导，我们需要两个状态表：
f[i]代表表示以i为结尾的最大乘积子数组
g[i]代表表示以i为结尾的最小乘积子数组
如图：

3、初始化：

初始化解决的是填表越界的问题
根据状态转移方程，我们需要初始化f[0]的位置
f[0] = g[0] = nums[0];

4、填表顺序：

从左往右

5、返回值：

返回f表中的最大值。

2、代码

  1. class Solution {
  2. public:
  3.     int maxProduct(vector<int>& nums) {
  4.         //1、创建dp表
  5.         int n = nums.size();
  6.         if(n == 1) return nums[0];
  7.  
  8.         vector<int > f(n);
  9.         auto g =f;
  10.  
  11.         //2、初始化
  12.         f[0] = g[0] = nums[0];
  13.  
  14.         //f[i]为最小值
  15.         //g[i]为最大值
  16.  
  17.         //3、填表
  18.         for(int i = 1; i<n; ++i)
  19.         {
  20.             f[i] = min(nums[i], min(g[i-1] * nums[i], f[i-1] * nums[i]));
  21.             g[i] = max(nums[i], max(f[i-1] * nums[i], g[i-1] * nums[i]));
  22.         }
  23.         
  24.         //4、返回值
  25.         int  ret = INT_MIN;
  26.         for(int i = 0; i<n; ++i)
  27.         {
  28.             if(g[i] >= ret) 
  29.                 ret = g[i];
  30.         }
  31.  
  32.         return ret;
  33.     }
  34. };
  35.

  题二十一 乘积为正数的最大子数组长度

1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode）

1、算法解析

一般来说，子数组系列的问题，使用动态规划思想来解决。
一般的dp状态就是：以i为结尾的，某某某。
同时把数组分成两种，如图：

一个是以i位置的元素，长度为1为一个结果
一个是以i-1以前，长度大于1作为一个结果

1、确定状态：

也是一个连续子数组求最大最小的问题。
我们创建一个一维f表。
f[i]的值，表示以i为结尾的最大乘积子数组为正数的长度。

2、状态转移方程：

i位置有两种状态：长度为1，长度大于1。
长度为1时，i位置有两种状态：一个是i位置本身为正数，或者是负数
长度大于1时，i位置也有两种状态：一个是i位置本身是正数*前面i-1序列中，最大乘积为正数的子数组长度+1
一个是i位置本身为负数*前面i-1序列中，最大乘积为负数的子数组长度+1
如图：

3、初始化：

初始化解决的是填表越界的问题
根据状态转移方程，我们需要初始化f[0]和g[0]的位置
f[0]记录正数，g[0]记录负数。
如果nums[0]为正数，g[0] = 0, f[0] = 1;
否则反之。

4、填表顺序：

从左往右

5、返回值：

返回f表中的最大值。

2、代码

  1. class Solution {
  2. public:
  3.     int getMaxLen(vector<int>& nums) {
  4.         //1、创建dp表
  5.         int n = nums.size();
  6.         vector<int> f(n), g(n);
  7.         if(n == 1) return nums[0] >= 0 ? 1 : 0;
  8.         
  9.         //2、初始化
  10.         g[0] = 1;
  11.         f[0] = 0;
  12.         if(nums[0] > 0)
  13.         {
  14.             g[0] = 0;
  15.             f[0] = 1;
  16.         }
  17.         else if(nums[0] == 0)
  18.         {
  19.             g[0] = f[0] = 0;
  20.         }
  21.  
  22.         //3、填表
  23.         int ret = INT_MIN;
  24.         for(int i = 1; i<n; ++i)
  25.         {
  26.             if(nums[i] < 0)
  27.             {
  28.                 f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
  29.                 g[i] = f[i-1] + 1;
  30.             }
  31.             else if(nums[i] > 0)
  32.             {
  33.                 f[i] = f[i-1] + 1;
  34.                 g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
  35.             }
  36.             ret = max(ret, f[i]);
  37.         }
  38.  
  39.         //4、返回值
  40.         return ret;
  41.     }
  42.         
  43. };
  44.

  题二十二 等差数列划分

413. 等差数列划分 - 力扣（LeetCode）

1、算法解析

1、确定状态：

也是一个连续子数组求最大最小的问题。
我们创建一个一维f表。
f[i]的值，表示以i为结尾的,所有为等差数组的子数组个数。
注意，是以i为结尾的等差数列，也就是说把i作为结尾。

2、状态转移方程：

以i为结尾，两种状态：
一是i和前面的两个i-1 i-1 构成等差数列
此时，在i-1为结尾的等差数组个数的基础上，再+1
因为把i-1为结尾的三个以上的子数组，再加上一个i位置，也构成等差数组，就是dp[i-1]
在此基础上，多了一个i-2 i-1 i 这一组等差数列
所以 dp[i] = dp[i-1] + 1

二是i和前面的而两个 i-1 i-2 不构成等差数列，此时，为0
如图：

3、初始化：

初始化解决的是填表越界的问题
根据状态转移方程，我们需要初始化:
dp[0] = 0
dp[1] = 0

4、填表顺序：

从左往右

5、返回值：

返回dp表的所有总和。

2、代码
 

  1. class Solution {
  2. public:
  3.     int numberOfArithmeticSlices(vector<int>& nums) {
  4.         //1、创建dp表
  5.         int n = nums.size();
  6.         if(n < 3 ) return 0;
  7.         vector<int> dp(n);
  8.  
  9.         //2、初始化
  10.         dp[0] = dp[1] = 0;
  11.  
  12.         //3、填表
  13.         for(int i = 2; i<n; i++)
  14.         {
  15.             dp[i] = nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ? dp[i-1] + 1 : 0;
  16.         }
  17.  
  18.         //4、返回值
  19.         int num = 0;
  20.         for(int i = 2; i<n; ++i)
  21.         {
  22.             num += dp[i];
  23.         }
  24.         return num;
  25.  
  26.  
  27.     }
  28. };

  题二十三 最长瑞流子数组

978. 最长湍流子数组 - 力扣（LeetCode）

最长瑞流子序列
直接确定状态：
dp[i]：表示以i为结尾的所有瑞流子序列中，最长的子序列。
再细分：
以i结尾的瑞流子序列，有两种状态：
一个是最后呈现“上升”，就是arr[i] > arr[i-1]
一个是最后呈现“下降”，就是arr[i] < arr[i-1]
所以，仅仅一个状态表无法全部表示
需要两个状态表
f[i]：最后是上升
g[i]：最后是下降

当时最后呈现上升时：
f[i] = g[i-1] + 1
当时最后呈现下降时：
g[i] = f[i-1] + 1

  1. class Solution {
  2. public:
  3.     int maxTurbulenceSize(vector<int>& arr) {
  4.         //1、创建dp表
  5.         int n = arr.size();
  6.         vector<int> f(n, 1), g(n, 1);
  7.  
  8.         //2、初始化
  9.  
  10.         //3、填表
  11.         int ret = 1;
  12.         for(int i = 1; i<n; ++i)
  13.         {
  14.             if(arr[i] > arr[i-1])
  15.             {
  16.                 f[i] = g[i-1] + 1;
  17.             }
  18.             else if(arr[i] < arr[i-1])
  19.             {
  20.                 g[i] = f[i-1] + 1;
  21.             }
  22.             ret = max(ret, max(g[i], f[i]));
  23.         }
  24.  
  25.         //4、返回值
  26.         return ret;
  27.  
  28.  
  29.  
  30.     }
  31. };

  题二十四 单词拆分

139. 单词拆分 - 力扣（LeetCode）


dp[i]：0到i的序列可以被字典中的单词组成
设一个j：表示最后一个单词的开始位置

dp[i]的值，等于dp[j]为true，并且[j+1,i]位置也可以被字典序组成
也就是说将整个字符串序列分成两个部分：最后一个单词+之前位置的是否能被构成。

  1. class Solution {
  2.         public:
  3.     bool wordBreak(string s, vector<string>& wordDict) {
  4.       //1、创建dp表
  5.       int n = s.size();
  6.       vector<bool> dp(n+1);
  7.       unordered_set<string> hash;
  8.       for(auto& e : wordDict)
  9.       {
  10.         hash.insert(e);
  11.       }
  12.       s = ' ' + s;
  13.  
  14.       //2、初始化
  15.         dp[0] = true;
  16.  
  17.       //3、填表
  18.         for(int i = 1; i<n+1; ++i)
  19.         {
  20.             for(int j = i; j>=1; j--)
  21.             {
  22.                 if(dp[j-1] && hash.count(s.substr(j, i-j+ 1)))
  23.                 {
  24.                     dp[i] = true;
  25.                     break;
  26.                 }
  27.             }
  28.         }
  29.  
  30.       //4、返回值
  31.       return dp[n];
  32.  
  33.     }
  34. };

  题二十五 环绕字符串中唯一的字串

467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode）

dp[i]：以i为结尾的所有字串的个数

i位置结尾：
长度为1

长度大于1 以i-1位置为前一个 dp[i] = dp[i-1] +  1

  1. class Solution {
  2. public:
  3.     int findSubstringInWraproundString(string s) {
  4.         //1、创建dp表
  5.         int n = s.size();
  6.         vector<int> dp(n,1);
  7.         if(n == 1) return 1;
  8.  
  9.         //2、初始化
  10.  
  11.         //3、填表
  12.         for(int i = 1; i<n; ++i)
  13.         {
  14.             if(s[i] - s[i-1] == 1 || (s[i-1] == 'z' && s[i] == 'a'))
  15.             { 
  16.                 dp[i] = dp[i-1] + 1;
  17.             }
  18.         }
  19.  
  20.         //4、返回值
  21.         int hash[26] = {0};
  22.         for(int i = 0; i<n; ++i)
  23.         {
  24.             hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
  25.             //dp[i] 的值，对应的就是s[i]为结尾的字串的结果
  26.         }
  27.  
  28.         int ret = 0;
  29.         for(int e : hash)
  30.         {
  31.             ret += e;
  32.         }
  33.         return ret;
  34.     }
  35. };

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号