[C国演义] 第十五章

最长湍流子数组

力扣链接

子数组 ⇒ 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;}
};

---

“殃莫大于叨天之功，罪莫大于掩人之善，恶莫深于袭下之能，辱莫重于忘己之耻，四者备而祸全。” — — 王阳明
译文：简译:最大的灾殃就是贪天之功，或将自己的功劳当成与天的功劳相当，最大的罪过就是埋没他人的善行，邪恶没有比偷袭别人的落难更大的，（或罪恶没有比乘人不备而进攻下属中的能人还深的），最大的耻辱就是忘记自己受到过的羞辱，这四者全都具备，各种灾祸就会降临。