jquery 素材的网站,软件外包公司如何接单,网站制作说明书,网站的策划方案文章目录 动态规划#xff08;子数组系列#xff09;1. 最大子数组和2. 环形子数组的最大和3. 乘积最大子数组4. 乘积为正的最长子数组的长度5. 等差数列划分6. 最长湍流子数组7. 单词拆分8. 环形字符串中的唯一的子字符串 动态规划#xff08;子数组系列#xff09;
1. 最… 文章目录 动态规划子数组系列1. 最大子数组和2. 环形子数组的最大和3. 乘积最大子数组4. 乘积为正的最长子数组的长度5. 等差数列划分6. 最长湍流子数组7. 单词拆分8. 环形字符串中的唯一的子字符串 动态规划子数组系列
1. 最大子数组和
题目链接 状态表示 dp[i]表示到 i 位置时所有子数组的最大和 如下展示的这样: 状态转移方程 初始化 为了方便初始化采用虚拟节点的方式这里初始化dp[0] 0 填表 从左到右 返回值 由于每个dp表里的每个值都表示到这个位置的最大子数组的和所有需要返回最大值
AC代码
class Solution
{
public:int maxSubArray(vectorint nums) {int n nums.size();vectorint dp(n 1);int ret -0x3f3f3f3f;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. 环形子数组的最大和
题目链接
分析题目这道题目可以取环形数组是不是可以像之间做的环形的打家劫舍题目一样来解决
还是分为两种情况来考虑 如果最大和是蓝色区域的部分只需要求出最大子数组的和就可以 如果是这样由于数组整体的和是固定的只需要求出中间的最小值然后相减即可 状态表示 讲过前面的题目分析发现这个题目需要两个状态表示 f[i]表示到 i 位置时所有子数组子数组和最大的值 g[i]表示到 i 位置时所有子数组子数组和最小的值 状态转移方程 初始化 采用虚拟节点的方式 填表 返回值 返回两种情况的较大值
AC代码
class Solution
{
public:const int N 0x3f3f3f3f;int maxSubarraySumCircular(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);int fMax -N, gMin N, sum 0;for (int i 1; i n; i){f[i] max(nums[i - 1], f[i - 1] nums[i - 1]);fMax max(fMax, f[i]);g[i] min(nums[i - 1], g[i - 1] nums[i - 1]);gMin min(gMin, g[i]);sum nums[i - 1];}if (sum gMin) return fMax;else return max(fMax, (sum - gMin));}
};3. 乘积最大子数组
题目链接 状态表示 f[i]表示以 i 为结尾所有子数组中最大乘积 g[i]表示以 i 为结尾所有子数组中最小乘积 状态转移方程 初始化 虚拟节点的方式为了不影响后续的填表采用f[0] 1, g[0] 1 填表 从左到右 返回值 返回乘积最大的即可
AC代码
class Solution
{
public:int maxProduct(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);f[0] g[0] 1;int ret -0x3f;for (int i 1; i n; i){if (nums[i - 1] 0){f[i] g[i - 1] * nums[i - 1];g[i] f[i - 1] * nums[i - 1];}if (nums[i - 1] 0){f[i] f[i - 1] * nums[i - 1];g[i] g[i - 1] * nums[i - 1];}f[i] max(nums[i - 1], f[i]);g[i] min(nums[i - 1], g[i]);ret max(ret, f[i]);}return ret;}
};4. 乘积为正的最长子数组的长度
题目链接 状态表示 f[i]表示以 i 位置为结尾所有子数组中乘积为正数的最大长度 g[i]表示以 i 位置为结尾所有子数组中乘积为负数的最大长度 状态转移方程 初始化 f[0] 1, g[0] 0 填表 返回值 返回乘积为正的最大长度
AC代码
class Solution
{
public:int getMaxLen(vectorint nums) {int n nums.size();vectorint f(n 1), g(n 1);int ret -0x3f3f3f3f;for (int i 1; i n; i){if (nums[i - 1] 0){f[i] max(1, f[i - 1] 1);g[i] max(0, g[i - 1] 0 ? 0 : g[i - 1] 1);}if (nums[i - 1] 0){f[i] max(0, g[i - 1] 0 ? 0 : g[i - 1] 1);g[i] max(1, f[i - 1] 1);}ret max(ret, f[i]);}return ret;}
};5. 等差数列划分
题目链接 状态表示 dp[i]表示到 i 位置时所有是等差数列子数组之和 状态转移方程 初始化 为了防止后续的填表不越界dp[0] 0, dp[1] 0 填表 从左到右 返回值 dp表的所有元素之和
AC代码
class Solution
{
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();vectorint dp(n);int sum 0;for (int i 2; i n; i){if (nums[i] - nums[i - 1] nums[i - 1] - nums[i - 2]){dp[i] dp[i - 1] 1;}sum dp[i];}return sum;}
};6. 最长湍流子数组
题目链接 状态表示 f[i] 以 i 位置为结尾的所有子数组当中最后呈现“上升” 状态下最长湍流子数组的长度 g[i] 以 i 位置为结尾的所有子数组当中最后呈现“下降”状态下最长湍流子数组的长度 状态转移方程 初始化 表里的数据都初始化为1 填表 从左到右 返回值 返回两个表的最大值
AC代码
class Solution
{
public:int maxTurbulenceSize(vectorint arr) {int n arr.size();vectorint f(n, 1), g(n, 1);int ret 1;for (int i 1; i n; i){if (arr[i] arr[i - 1]) f[i] g[i - 1] 1;else if (arr[i] arr[i - 1]) g[i] f[i - 1] 1;ret max(ret, max(f[i], g[i]));}return ret;}
};7. 单词拆分
题目链接 状态表示 dp[i] 表示0到i之间的字符串能否被字典拼接 状态转移方程 初始化 可以在字符串s前面加上一个占位符这样就可以没有下标的映射关系 填表 从左到右 返回值
AC代码
class Solution
{
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring hash;for (auto e : wordDict) hash.insert(e);int n s.size();vectorbool dp(n 1);dp[0] true;s s;for (int i 1; i n; i){for (int j i; j 1; j--){if (dp[j - 1] hash.count(s.substr(j, i - j 1))){dp[i] true;break;}}}return dp[n];}
};8. 环形字符串中的唯一的子字符串
题目链接 状态表示 dp[i]表示到 i 位置的所有子串当中有多少个在base中出现过 状态转移方程 初始化 初始化为1 填表 返回值 由于dp表当中存的值可能是重复的所以需要进行去重操作。相同字符串结尾的dp值取最大的值即可
AC代码
class Solution
{
public:int findSubstringInWraproundString(string s) {int n s.size();vectorint dp(n, 1);for (int i 1; i n; i){if ((s[i - 1] 1 s[i]) || (s[i - 1] z s[i] a)){dp[i] dp[i - 1] 1;}}int hash[26] {0};int sum 0;for (int i 0; i n; i){hash[s[i] - a] max(hash[s[i] - a], dp[i]);}for (auto x : hash) sum x;return sum;}
};
