题目思路与代码全解析

一、问题核心分析

题目要求将字符串划分为若干无重复字符的连续子串，并最大化子串价值之和（长度为$i$的子串价值为$a_i$）。核心难点在于：

1. 子串必须满足「内部无重复字符」的约束；
2. 需在满足约束的前提下，通过动态规划找到价值最大化的划分方式；
3. 数据范围$n \le 10^5$，需注意时间复杂度优化（原代码未做极致优化，后文会补充）。

二、动态规划（DP）核心思路

1. DP数组定义

定义dp[i]表示：字符串前$i$个字符（$s[1..i]$，代码中字符串下标从1开始）划分后的最大价值和。 目标：求dp[n]（整个字符串的最大价值）。

2. 初始状态

dp[0] = 0：前0个字符（空串）没有子串，价值和为0。

3. 状态转移逻辑

对于第$i$个字符，我们需要考虑所有合法的划分终点：

• 基础情况：将第$i$个字符单独划分为一个子串，此时dp[i] = dp[i-1] + a[1]（长度1的子串价值为$a_1$）；
• 扩展情况：从$i-1$往前找$j$（$j \ge 1$），若子串$s[j..i]$中无重复字符，则尝试更新dp[i] = max(dp[i], dp[j-1] + a[i-j+1])（$i-j+1$是子串长度，对应价值$a_{i-j+1}$）；
• 终止条件：当$s[j]$在$s[j..i]$中重复时，停止往前找$j$（因为更前面的$j' < j$会包含重复字符，子串$s[j']..i$必然不合法）。

4. 关键优化点

小写字母仅有26个，因此每个$i$往前最多遍历26个字符就会遇到重复（无重复子串的最大长度为26）。利用这一特性，可将内层循环的时间复杂度从$O(n)$降为$O(26)$，最终总时间复杂度为$O(n)$，适配$n=10^5$的规模。

三、代码逐行解析

四、样例1验证（理解执行过程）

输入样例1

6
street
2 1 7 4 3 3

• 字符串：s[1]='s', s[2]='t', s[3]='r', s[4]='e', s[5]='e', s[6]='t'
• 价值数组：a[1]=2, a[2]=1, a[3]=7, a[4]=4, a[5]=3, a[6]=3

关键步骤计算

最终dp[6]=13，与样例输出一致。