53. 最大子数组和 - 力扣LeetCodeclass Solution { public: const int INF 0x3f3f3f3f; int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n 1); dp[0] -INF; int ret -INF; for (int i 1; i n; i) { dp[i] max(dp[i - 1] nums[i - 1], nums[i - 1]); ret max(ret, dp[i]); } return ret; } }; // dp[i] 表示以i位置为结尾前面所有子数组中的和最大的那一个子数组的和 // dp[i]由前面dp[i-1]推出 dp[i-1] nums[i]表示以i结尾长度大于1的子数组的最大和 可以不选前面的dp[i-1]那么直接就是nums[i] 表示以i位置结尾长度为1的子数组的最大值 // 初始化前面多开一个 将dp[0]设置为很大的一个负数 保证数组中的负数参与运算 // 最终结果可能是负数 那么ret也设置为一个很大的负数 保证取得到dp表中的数据918. 环形子数组的最大和 - 力扣LeetCodeclass Solution { public: int maxSubarraySumCircular(vectorint nums) { int n nums.size(); vectorint f(n 1), g(n 1); // 分别存以i结尾的最大最小子数组和 f[0] 0; g[0] 0; int fmax INT_MIN, gmin 0, sum 0; for (int i 1; i n; i) { f[i] max(nums[i - 1], f[i - 1] nums[i - 1]); //cout f[i]; g[i] min(nums[i - 1], g[i - 1] nums[i - 1]); fmax max(fmax, f[i]); gmin min(gmin, g[i]); sum nums[i - 1]; } // cout endl; // cout sum fmax gmin; // 当全部是负数的时候 返回的是0 因为max(fmax, sum-gmin)的时候fmax是负数 sum-gmin是0 而子数组非空 所以要特殊处理 此时直接返回fmax即可 return sum - gmin 0 ? fmax : max(fmax, sum - gmin); } }; // 第一种情况和最大子数组和一样 // 出现环形最大的情况如何解决转换视角 因为这段环形区域一首一尾 很不好求 那么可以求中间的部分 因为数组的总和的固定的 当环形数组和最大的时候 中间连续的部分就是最小的 因此可以求最小子数组和 // 最终结果求两者之间最大值即可152. 乘积最大子数组 - 力扣LeetCode// 简化代码 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 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; } }; // class Solution // { // public: // int maxProduct(vectorint nums) // { // int n nums.size(); // vectorint f(n1), g(n1); // int ret INT_MIN; // for (int i 1; i n; i) // { // if (nums[i-1] 0) // { // int fi 0; // if (f[i-1] 0) // { // fi max(fi, f[i-1] * nums[i-1]); // } // if (g[i-1] 0) // { // fi max(fi, g[i-1] * nums[i-1]); // } // fi max(fi, nums[i-1]); // f[i] fi; // int gi nums[i-1]; // 若是f[i-1] g[i-1]都大于0 则直接填入nums[i-1] // if (f[i-1] 0) // { // gi min(gi, f[i-1] * nums[i-1]); // } // if (g[i-1] 0) // { // gi min(gi, g[i-1] * nums[i-1]); // } // gi min(gi, nums[i-1]); // g[i] gi; // } // else if (nums[i-1] 0) // { // int fi nums[i-1];// 若是f[i-1] g[i-1]都大于0 则直接填入nums[i-1] // if (f[i-1] 0) // { // fi max(fi, f[i-1] * nums[i-1]); // } // if (g[i-1] 0) // { // fi max(fi, g[i-1] * nums[i-1]); // } // fi max(fi, nums[i-1]); // f[i] fi; // int gi 0; // if (f[i-1] 0) // { // gi min(gi, f[i-1] * nums[i-1]); // } // if (g[i-1] 0) // { // gi min(gi, g[i-1] * nums[i-1]); // } // gi min(gi, nums[i-1]); // g[i] gi; // } // else // { // f[i] g[i] 0; // } // ret max(ret, f[i]); // } // return ret; // } // }; // f[i]表示以i结尾最大的子数组乘积 // g[i]表示以i结尾最小的子数组乘积 // 因为可能出现负数和负数相乘为最大结果的出现因此要将子数组最小乘积也记录下来 // 当nums[i]为正数的时候 找前面的最大乘积 为负数时 找前面的最小乘积 // 状态转移方程 // nums[i]为正数 那么f[i]就从f[i-1]和g[i-1]里面找有没有同号的 有则相乘填入f[i] 没有则f[i]nums[i] 不用看有没有0 nums[i]是正数 保证最大 g[i]则是找有没有异号的 有则相乘填入g[i] 没有则看f[i-1]g[i-1]有没有0 有则g[i]0 没有则g[i]nums[i] // 当nums[i]为负数的时候 f[i]看f[i-1]g[i-1]里面有没有同号的有则相乘填入f[i]没有则看f[i-1]g[i-1]有没有0 有则f[i]0 没有则f[i]nums[i] g[i]则是看有没有异号的 有则相乘填入 没有则直接g[i]nums[i] 不用看有没有0 nums[i]是负数 保证最小 // 当nums[i]为0的时候 f[i] g[i]都填01567. 乘积为正数的最长子数组长度 - 力扣LeetCodeclass Solution { public: int getMaxLen(vectorint nums) { int n nums.size(); vectorint f(n 1), g(n 1); int ret 0; 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; } }; // 定义f[i]为以i位置为结尾乘积为正数的最长子数组的长度 // 状态推导 // 当nums[i]0时 长度可以是1 直接选取nums[i] 长度可以大于1 由前面推来 f[i] f[i-1]1 // 当nums[i]0时 长度不能是1 长度可以大于1 由前面推来 但是前面必须是乘积为负数最长子数组的长度 因此引入g[i] f[i] g[i-1] 1 但是当前面乘积也大于零的时候g[i-1]0 f[i]1了 此时Nums[i]是负数 不合逻辑 因此特殊处理 g[i]0时 f[i]1 // g[i]的推导同样如此 当nums[i] 大于0时 长度不能为1 长度可以大于1 g[i] g[i-1]1 g[i-1]0的时候特殊处理 // nums[i]小于0时 长度可以是1 长度可以大于1 g[i] f[i-1] 1 // 状态转移方程 // nums[i-1]0 f[i] f[i-1]1 g[i] g[i-1]0?0:g[i-1]1 // nums[i-1]0 f[i] g[i-1]0?0:g[i-1]1 g[i]f[i-1]1 // 初始化 // 当nums[0]大于0的时候 f[1]等于1 g[1]0 nums[0]小于0的时候 f[i]0 g[i]1 那么按照方程f[0] g[0]都初始化为0即可413. 等差数列划分 - 力扣LeetCodeclass Solution { public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); if (n 2) return 0; vectorint dp(n); dp[0] dp[1] 0; int ret 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; else dp[i] 0; ret dp[i]; } return ret; } }; // dp[i]表示以i位置结尾的子数组中有多少个等差数组 // 如何根据dp[i-1]推出dp[i] 假设nums[i-2]a, nums[i-1]b nums[i]c // ...... a b 是等差数组 若是c和a b也构成等差数组那么c也和......a b 构成等差数组 // 因此只需要判断abc是否构成等差数组即可 若构成 那么dp[i] dp[i-1] 1 dp[i-1]表示在很多个a b 结尾的等差数组后面加上一个和a b构成等差数组的c 那么此时以c结尾的子数组中等差数组个数和以b结尾的一样 1表示a b c 也是一个等差数组 并且是以b为结尾中没有的 新出的 因此要1 // 当abc不是等差数组时 dp[i]0 子数组必须连续 和c连续的ab都不行 前面也不行 // 初始化 等差数组至少有三个元素 因此dp[0]dp[1]0; // 返回值 加上每个位置为结尾的子数组中等差数组的个数978. 最长湍流子数组 - 力扣LeetCodeclass Solution { public: int maxTurbulenceSize(vectorint nums) { int n nums.size(); if (n 1) return 1; else if (n 2) return nums[0] nums[1] ? 1 : 2; else { vectorint dp(n); dp[0] 1; dp[1] nums[0] nums[1] ? 1 : 2; int ret 1; for (int i 2; i n; i) { if ((nums[i] nums[i - 1] nums[i - 1] nums[i - 2]) || (nums[i] nums[i - 1] nums[i - 1] nums[i - 2])) dp[i] dp[i - 1] 1; else { if (nums[i] nums[i - 1]) dp[i] 1; else dp[i] 2; } ret max(ret, dp[i]); } return ret; } return 1; } }; // dp[i]表示以i为结尾的子数组中最长湍流子数组的长度 // 状态推导 当(nums[i] nums[i-1] nums[i-1] nums[i-2]) || (nums[i] nums[i-1] nums[i-1] nums[i-2]) 时 // dp[i] dp[i-1] 1 // 否则dp[i] 2 和前面一个可以构成 // 和前面元素相等的情况下 dp[i] 1 // 初始化 dp[0] 1 dp[1] nums[0]nums[1] ? 1 : 2139. 单词拆分 - 力扣LeetCodeclass Solution { public: bool wordBreak(string s, vectorstring wordDict) { unordered_setstring hash; for (auto str : wordDict) hash.insert(str); int n s.size(); vectorbool dp(n 1, false); dp[0] true; s s; for (int i 1; i n; i) { for (int j i; j 0; j--) { if (dp[j - 1] hash.count(s.substr(j, i - j 1))) { dp[i] true; break; } } } return dp[n]; } }; // dp[i] 表示s的 1 ~ n之间的子串可以在字典中找到 dp[i] true // 那么最终返回dp[n] // dp[i]如何由前面推出 1~i之间的子串可以分为两部分 1~j-1 j~i 当这两部分都可以由字典中的单词组成时 dp[i] true 反之false 1jij是变化的 // 那么1~j-1实际上就是dp[j-1] j~i这个子串可以遍历字典看有没有这个子串对应的单词 这两者同时成立 dp[i]true // 初始化 因为使用到j-1 dp表多开一个位置 dp[0]设置为true 没有实际意义 单纯是不影响后面填表 避免后面的全为false // 下标映射 为了对其 可以在s前面加上一个空格字符 这样下标处理更简单 // 优化 可以用哈希表记录下来字典中单词出现与否 避免循环查找 // 每次填表一旦有一种j满足dp[i]true直接跳出此循环 // 线性dp由前面状态推出当前状态的时候 可以循环前面的所有dp的位置来看当前dp的值 不一定是简单的dp[i-1]得到dp[i]467. 环绕字符串中唯一的子字符串 - 力扣LeetCodeclass Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); vectorint dp(n 1, 1); s s; int ans[26] { 0 }; for (int i 1; i n; i) { if (s[i] s[i - 1] 1 || (s[i - 1] z s[i] a)) dp[i] dp[i - 1]; ans[s[i] - a] max(ans[s[i] - a], dp[i]); } int ret 0; for (int i 0; i 26; i) ret ans[i]; return ret; } }; // dp[i]表示以当前位置结尾的字符串在环绕字符串中有多少个 // 长度为1必然存在 长度大于一需要借助dp[i-1]推导 只有当前面的字符和当前字符能够组成在环绕字符串中出现的字符时 dp[i]dp[i-1]1 // 初始化 使用到dp[i-1]因此需要多开一个位置 dp[0]1 对后序填表无影响 // 重复出现的子串只统计一次 因此需要处理 当存在相同字符结尾的字符串时 长的那一个的子串一定包含短的那一个的所有字串 例如 a,b,c 和 y,z,a,b,c 后面一定包含前面所有字串 因此当存在相同字符结尾的字符串时 只需要统计dp值大的那一个 可以开一个数组记录字符结尾的最大的dp值 // 返回值 返回数组中的和