企业官网建设流程全解析

一、题目

二、做题思路

2.1 状态表示（核心基础）

本题要求计算最长摆动子序列的长度。摆动序列要求相邻差值正负交替，因此需要区分最后一段差值的符号。我们定义两个状态：

• f[i]表示以nums[i]结尾，且最后一段为“上升”（即前一个元素小于当前元素）的摆动序列的最大长度。

• g[i]表示以nums[i]结尾，且最后一段为“下降”（即前一个元素大于当前元素）的摆动序列的最大长度。

2.2 状态转移方程（关键难点）

要构造以nums[i]结尾的摆动序列，需要枚举其前一个元素nums[j]（j < i），并根据大小关系决定如何转移：

• 若nums[i] > nums[j]（当前为上升），则可以将nums[i]接在以nums[j]结尾且最后一段为下降的序列后面，长度更新为f[i] = max(f[i], g[j] + 1)。

• 若nums[i] < nums[j]（当前为下降），则可以将nums[i]接在最后一段为上升的序列后面，长度更新为g[i] = max(g[i], f[j] + 1)。

• 若相等，无法形成摆动，跳过。
  该方程通过枚举所有可能的前驱，保证了子序列的顺序不变性和差值交替性。

2.3 初始化（边界防护）

每个元素自身可以单独构成长度为 1 的摆动序列（既可作为上升起点也可作为下降起点），因此f[i] = g[i] = 1（对所有i）。

2.4 填表顺序（递推方向）

f[i]和g[i]依赖所有j < i的状态，因此必须从左到右（即i从 1 到n-1）依次填充，且对于每个i，内层遍历所有j < i，确保每个状态计算时，其所有前置状态均已就绪。

2.5 返回值（目标映射）

题目要求返回最长摆动子序列的长度，即所有f[i]和g[i]中的最大值。我们在计算完成后遍历取最大值，最终返回ret。

三、代码

class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); // 边界处理：空数组无摆动序列 if (n == 0) return 0; // 1. 创建dp表 // f[i] : 以 nums[i] 结尾，且最后一段比较关系为“上升”（nums[i-1] < nums[i]）的摆动序列的最大长度 // g[i] : 以 nums[i] 结尾，且最后一段比较关系为“下降”（nums[i-1] > nums[i]）的摆动序列的最大长度 // 初始化：每个元素自身可构成长度为 1 的摆动序列（既可以是上升也可以是下降的起点） vector<int> f(n, 1); vector<int> g(n, 1); // 2. 填表顺序：从左到右（i 从 1 到 n-1），因为 f[i]/g[i] 依赖所有 j < i 的状态 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // 3. 状态转移方程： // 若 nums[i] > nums[j]，则可以将 nums[i] 接在“下降”结尾的序列后面（g[j]），形成上升结尾的序列， // 长度 = g[j] + 1；同时保留 f[i] 原有的值（可能通过其他 j 得到更长的长度） if (nums[i] > nums[j]) { f[i] = max(f[i], g[j] + 1); } // 若 nums[i] < nums[j]，则可以将 nums[i] 接在“上升”结尾的序列后面（f[j]），形成下降结尾的序列， // 长度 = f[j] + 1；同时保留 g[i] 原有的值 else if (nums[i] < nums[j]) { g[i] = max(g[i], f[j] + 1); } // 若相等，无法构成摆动，跳过（状态保持不变） } } // 4. 返回值：所有 f[i] 和 g[i] 中的最大值 int ret = 1; for (int i = 0; i < n; i++) { ret = max(ret, max(f[i], g[i])); } return ret; } };

四、流程图

五、题目

六、做题思路

6.1 状态表示（核心基础）

本题要求返回最长递增子序列的个数，因此需要同时记录以每个位置结尾的最长长度和对应的个数。
定义两个数组：

• len[i]：以nums[i]结尾的最长递增子序列的长度。

• count[i]：以nums[i]结尾且长度为len[i]的递增子序列的个数。

6.2 状态转移方程（关键难点）

枚举前驱位置j < i，若nums[i] > nums[j]，则可以将nums[i]接在nums[j]后面：

• 若len[j] + 1 == len[i]，说明找到另一种方式达到相同的最长长度，count[i] += count[j]。

• 若len[j] + 1 > len[i]，说明找到了更长的子序列，更新len[i] = len[j] + 1，count[i] = count[j]。

• 若len[j]+1 < len[i]，则忽略。

6.3 初始化（边界防护）

每个元素自身构成长度为 1 的子序列，且只有 1 种方式，因此len[i] = count[i] = 1（对所有i）。

6.4 填表顺序（递推方向）

len[i]和count[i]依赖所有j < i的状态，因此从左到右遍历i，内层遍历所有j < i，确保前置状态已就绪。

2.5 返回值（目标映射）

遍历所有位置，找出全局最大的len[i]，并将所有等于该最大长度的count[i]累加，返回该累加和。

七、代码

class Solution { public: int findNumberOfLIS(vector<int>& nums) { int n = nums.size(); // 1. 创建dp表（两个一维数组） // len[i] : 以 nums[i] 结尾的最长递增子序列的长度 // count[i]: 以 nums[i] 结尾的最长递增子序列（长度为 len[i]）的个数 vector<int> len(n, 1); // 每个元素自身构成长度为1的子序列 vector<int> count(n, 1); // 每个元素自身构成1种长度为1的子序列 // 2. 填表顺序：从左到右（i 从1到n-1），因为 len[i] 和 count[i] 依赖所有 j < i 的状态 for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { // 只有 nums[i] > nums[j] 时才能将 i 接在 j 后面形成递增 if (nums[i] > nums[j]) { // 3. 状态转移方程： // 如果通过 j 能达到的长度（len[j]+1）等于当前已知的以 i 结尾的最长长度 len[i]， // 说明找到了另一种方式形成相同长度的 LIS，累加其个数。 if (len[j] + 1 == len[i]) { count[i] += count[j]; } // 如果通过 j 能达到的长度（len[j]+1）大于当前已知的最长长度 len[i]， // 说明找到了更长的 LIS，更新 len[i] 和 count[i]。 else if (len[j] + 1 > len[i]) { len[i] = len[j] + 1; count[i] = count[j]; } // 若 len[j]+1 < len[i]，则忽略，不影响当前最长。 } } } // 4. 收集全局结果：找出所有长度中的最大值及其对应的总个数 int retLen = 1; // 全局最长递增子序列长度（初始至少为1） int retCount = 1; // 全局最长递增子序列的总个数 for (int i = 0; i < n; i++) { if (len[i] > retLen) { retLen = len[i]; retCount = count[i]; } else if (len[i] == retLen) { retCount += count[i]; } } // 5. 返回值：最长递增子序列的个数 return retCount; } };

八、流程图