最长湍流子数组
子数组 ⇒ dp[i]的含义: 以arr[i] 结尾的所有子数组中的最长湍流子数组的长度
子数组 ⇒ 状态转移方程根据 最后一个位置来划分👇👇👇
- 初始化:
都初始化为1 ⇒ 1. 一个数字也是一个湍流子数组. 2. 可以少考虑四种状态 - 遍历方向:
从前往后遍历 - 返回结果:
返回g表 和 f表中的最大值
class Solution { public: int maxTurbulenceSize(vector<int>& arr) { int n = arr.size(); // 建表 + 初始化 vector<int> f(n, 1), g(n, 1); int res = 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; res = max(res, max(f[i], g[i])); } return res; } };
环绕字符串中唯⼀的⼦字符串
子数组 ⇒ dp[i]的含义 以s[i] 结尾的所有子数组中环绕字符串的最长长度
状态转移方程:
- 初始化:
都初始化为1 ⇒ 1. 一个字符也满足环形子数组的条件, 2. 少考虑两种状态 - 遍历方向:
从前往后 - 返回结果:
去重dp[i] + 累加dp[i]
class Solution { public: int findSubstringInWraproundString(string s) { int n = s.size(); // 建表 + 初始化 vector<int> dp(n, 1); 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] + 1; } // 去重 -- 找到每个字母结尾的最大长度 int hash[26] = {0}; for(int i = 0; i < n; i++) { hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]); } // 统计结果 int res = 0; for(auto e : hash) { res += e; } return res; } };
