hk网站域名百度搜索引擎广告投放

1.最大子数组

题目链接：53. 最大子数组和 - 力扣（LeetCode）

题目描述：找出nums数组中的最大和连续数组，并返回其最大和

算法讲解：动态规划

1.状态表示：经验+题目要求

经验：以某位置为结尾，什么什么什么

在这道题中，因为要找出最大和的连续子数组，并返回这个最大和，所以在这道题中，可以将dp[i]表示为：以i位置为结尾的所有子数组中的最大和

2.状态转移方程：

做这种线性dp的问题，要画图来分析，由于要找出以i位置为结尾的所有子数组的最大和，首先就要找出nums数组所有以i为结尾的子数组，此时找出的子数组可以划分为两种情况，一种是长度为1的子数组，另一种情况是长度大于1的子数组。

第一种情况：长度为1的子数组

长度为1的子数组就是nums[i]，此时的子数组的最大和就是nums[i]，所以此时dp[i]=nums[i]

第二种情况：长度大于1的子数组

当子数组的长度大于1时，此时子数组可以看成由一个以单独nums[i]组成的数组和一个以i-1的位置为结尾的数组组成的数组，如下图

此时要想求dp[i]，此时就要知道以i-1位置为结尾的子数组的最大和，根据状态表示，可以用dp[i-1]表示以i-1位置为结尾的子数组的最大和，此时dp[i]=dp[i-1]+nums[i]

因为要求的是最大和，所以最终的状态转移方程为：

dp[i]=Math.max(nums[i]，dp[i-1]+nums[i]) 

3.初始化 

此时由于求dp[i]时会用到dp[i-1]，所以要初始化dp[0]，dp[0]表示以第1个位置为结尾的所有子数组的最大和，因为0是数组的起始位置，此时就要将dp[0]=nums[0]

4.填表顺序

从左往右填dp表即可

5.返回值

要返回dp表中的最大值

代码实现：

//暴力枚举
class Solution {public int maxSubArray(int[] nums) {int n=nums.length;int ret=Integer.MIN_VALUE;int sum=0;for(int i=0;i<n;i++){for(int j=i;j<n;j++){if(i==j) sum=0;sum+=nums[j];ret=Math.max(ret,sum);}}return ret;}
}//动态规划
class Solution {public int maxSubArray(int[] nums) {int n=nums.length;int[] dp=new int[n];dp[0]=nums[0];for(int i=1;i<n;i++)dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);int ret=dp[0];for(int i=0;i<n;i++)if(ret<dp[i]) ret=dp[i];return ret;}
}

2.环形数组的最大和 

题目链接：918. 环形子数组的最大和 - 力扣（LeetCode） 

 题目解析：不用看图片中的题目，看也看不懂，只需要知道nums是一个环形数组就行了

算法讲解：

1.状态表示：

首先分析一下题目，由于nums数组是一个环形数组，所以在环形数组中选择的子数组会有两种情况，如下图

第一种情况就是子数组是在nums中的蓝色部分，此时直接求出蓝色部分的子数组中最大和即可

第二种情况就是选中的子数组，一部分是在尾部，一部分在头部，因为是环形数组，所以这两部分也是连续的，但是此时直接求出最大和是有点困难的，但是可以装换一下思路， 因为nums数组的总和是固定的，此时要求最大和，只要求出中间那部分子数组中的最小和，通过总和减去中间部分的最小和，可以间接得到最大和，如下图

所以，此时就会有两种状态表示：

f[i]表示：以i位置为结尾的所有子数组中的最大和

g[i]表示：以i位置为结尾的所有子数组中的最小和 

2.状态转移方程

因为有两个状态表示，所以状态转移方程也有两种

推算f[i]，推算f[i]时，子数组也可以分为两种，分别是长度为1的子数组和长度不为1的子数组，如下图

当子数组的长度为1时，此时子数组就是nums[i]，所以此时f[i]=nums[i]

当子数组的长度大于1时，此时要计算f[i]，就要知道以i-1位置为结尾的所有子数组中的最大和，根据f[i]的状态表示，f[i-1]可以表示以i-1位置为结尾的所有子数组中的最大和，此时f[i]=f[i-1]+nums[i] 

因为要求的是最大和，所以f[i]的状态转移方程为：

f[i]=Math.max(nums[i]，nums[i]+f[i-1])

推理g[i]的状态转移方程的过程一模一样，同理可得：

g[i]=Math.min(nums[i]，nums[i]+g[i-1]) 

3.初始化

此时为了方便初始化，可以多创建一部分空间来实现初始化，初始化时有两个注意事项：

第一个注意事项：虚拟空间填的值要保证后面的填表正确

假设没有多创建空间，原本f[0]和g[0]要填的值就是nums[0]，如果多创建了空间后，原本的f[0]和g[0]就变成了f[1]和g[1]，此时的f[0]和g[0]就是多创建的空间，此时要想nums[0]被选上，只要将f[0]和g[0]初始化为0即可，因为nums[0]+0的结果还是nums[0]

4.填表顺序

由于填表时用到了i-1，所以要从左往右填表

5.返回值

此时是有一个细节的，如果nums数组中全是负数，此时直接返回fmax即可，如果数组中不全是负数，返回Math.max(fmax，sum-gmin)即可

代码实现：

//我写的版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int n=nums.length;if(n==1) return nums[0];int sum=0;for(int i=0;i<n;i++) sum+=nums[i];int[] f=new int[n+1];int[] g=new int[n+1];f[0]=g[0]=0;for(int i=1;i<n+1;i++){f[i]=Math.max(nums[i-1],f[i-1]+nums[i-1]);g[i]=Math.min(nums[i-1],g[i-1]+nums[i-1]);}int max=Integer.MIN_VALUE;int min=Integer.MAX_VALUE;for(int i=1;i<n+1;i++){if(max<f[i]) max=f[i];if(min>g[i]) min=g[i];}return sum==min?max:Math.max(max,sum-min);}
}//另一个版本
class Solution {public int maxSubarraySumCircular(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];int max=Integer.MIN_VALUE;int min=Integer.MAX_VALUE;int sum=0;for(int i=1;i<n+1;i++){int x=nums[i-1];f[i]=Math.max(nums[i-1],nums[i-1]+f[i-1]);max=Math.max(max,f[i]);g[i]=Math.min(nums[i-1],nums[i-1]+g[i-1]);min=Math.min(min,g[i]);sum+=x;}return sum==min ? max : Math.max(max,sum-min);}
}

3.乘积最大子数组 

题目链接：152. 乘积最大子数组 - 力扣（LeetCode） 

题目描述：在nums数组中找出一个非空连续子数组，且该子数组的乘积最大，并返回该子数组的乘积

算法讲解：动态规划

1.状态表示

其实这道题和第二道题很相似，一开始肯定只会想到用一个dp[i]来表示以i位置为结尾的所有子数组的最大和，但是这道题求的是乘积，且nums数组中的nums[i]可能出现负数的情况，当f[i]是一个很大的数时，如果接着遇到nums[i]是一个负数，那么之后f[i]就会变成一个很小的数，所以此时还要记录以i位置为结尾的的所有子数组中的最小和，所以最终的状态表示有2个：

f[i]表示：以i位置为结尾的所有子数组中的最大乘积

g[i]表示：以i位置为结尾的所有子数组总的最小乘积

2.状态表示

因为状态表示有两个，所以推算状态方程时也有两种

1.推算f[i]的状态转移方程

在推算f[i]时，子数组也可以分为2种情况，可以分为长度为1的子数组和长度大于1的子数组，如下图

当子数组的长度为1时，此时nums[i]就是子数组，此时f[i]=nums[i] 

当子数组的长度不为1时，如果按照我们平时的惯性思维，此时要求f[i]，就要先求出f[i-1]，也就是要求出以i-1位置为结尾时的所有子数组中的最大乘积，此时就得出f[i]=f[i-1]*nums[i]，但是这一道题的nums[i]有可能是负数的情况，一个小的数与一个负数相乘就会变成一个大的数，而g[i]就表示以i位置为结尾的所有子数组中的最小乘积，所以此时f[i]=g[i-1]*nums[i]

如下图：

但是要求的是最大乘积，所以最终f[i]的状态转移方程为：

f[i]=max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]) 

同理可得，g[i]的状态转移方程：

g[i]=min(nums[i],g[i-1]*nums[i-1],f[i-1]*nums[i-1]) 

3.初始化

在这里，依旧选择创建虚拟节点来实现初始化，有两个注意事项：

第一个注意事项：虚拟节点填的值要保证后面的天表正确

填加了虚拟节点后，此时的f[1]就是原来的f[0]，此时初始化f[1]时，是要将f[1]初始化为nums[0]的，但是初始化时用到了f[i]=max(nums[i],f[i-1]*nums[i],g[i-1]*nums[i]) ，此时要保证max时让nums[i]被选到，此时直接将f[0]和g[0]初始化为1就行了，因为nums[i]*1的结果也是nums[i]

第二个注意事项：注意下标的映射关系

4.填表顺序

要从左往右同时填f表和g表

5.代码实现

class Solution {public int maxProduct(int[] nums) {int n=nums.length;if(n==1) return nums[0];int[] f=new int[n+1];int[] g=new int[n+1];f[0]=1;g[0]=1;int ret=Integer.MIN_VALUE;for(int i=1;i<n+1;i++){f[i]=Math.max(nums[i-1],Math.max(f[i-1]*nums[i-1],g[i-1]*nums[i-1]));g[i]=Math.min(nums[i-1],Math.min(g[i-1]*nums[i-1],f[i-1]*nums[i-1]));if(f[i]>ret) ret=f[i];}return ret;}
}

4.乘积为正数的最长子数组的长度 

题目链接：1567. 乘积为正数的最长子数组长度 - 力扣（LeetCode） 

题目描述：返回nums数组中乘积为正数的最长子数组的长度

算法讲解：动态规划

1.状态表示：经验+题目要求

根据题目要求，首先会设计出一个状态表示，用f[i]来表示：

f[i]表示：以i位置为结尾的所有子数组中乘积为正数的最长长度

g[i]表示：以i位置为结尾的所有子数组中乘积为负数的最长长度

2.状态转移方程：

因为是子数组问题，子数组的情况任然可以分为2中情况，分别是长度为1的子数组和长度大于1的子数组，如下图

推算f[i]：

第一种情况：子数组长度为1时

当子数组的长度为1时，也是有两种情况的，分别是nums[i]大于0和nums[i]<0的情况。

当nums[i]>0时，此时f[i]=1，当nums[i]<0时，此时f[i]=0 

当子数组的长度大于1时，也是有两种情况的，分别是nums[i]大于0和nums[i]<0的情况。

当nums[i]>0时，此时首先要知道以i-1位置为结尾的所有子数组中乘积为正数的最长长度，根据f[i]的状态表示，可以用f[i-1]来表示以i-1位置为结尾的所有子数组中乘积为正数的最长长度，此时，f[i]=f[i-1]+1

当nums[i]<0时，因为f[i]表示以i位置为结尾的所有子数组中乘积为正数的最长长度，因为正数*负数等于负数，所以此时还要知道以i-1为位置为结尾的所有子数组中乘积为负数的最长长度，所以此时还要另外设计一个状态表示，用g[i]表示以i位置为结尾的所有子数组中乘积为负数的最长长度，此时就可以用g[i-1]来表示以i-1为位置为结尾的所有子数组中乘积为负数的最长长度，此时惯性思维就直接让f[i]=g[i-1]+1了，但是这样是不对的，如果g[i-1]==0，说明i位置前面的数字全是正数相乘，如果此时nums[i]<0的话，此时f[i]是等于0的，因为子数组都要包含i位置这个数据，如果按照上面的f[i]=g[i-1]+1，此时计算的f[i]是等于1的，所以此时的状态转移方程为：

f[i] = g[i-1]==0 ? 0 : g[i-1]+1

分析总结图如下

所以此时在推算状态转移方程时，也要分为2中情况

第一种情况：nums[i]>0时，此时f[i]=Math.max(1,f[i-1]+1)，可以简化成f[i]=f[i-1]+1

第二种情况：nums[i]<0时，此时f[i]=Math.max(0,g[i-1]==0?0:g[i-1]+1) ，可以简化成f[i]=g[i-1]==0?0:g[i-1]+1

如下图：

推算g[i]:

此时推算g[i]的过程和上面一模一样，有一个细节不同

不同之处：

当子数组的长度>1时，此时推算g[i]时，有一个nums[i]>0的情况，此时可能惯性思维直接推出g[i]=g[i-1]+1，但是这是不对的，如果此时g[i-1]==0，说明前面都是正数相乘，此时再加上nums[i]>0，此时g[i]是等于0的，如果根据上面的g[i]=g[i-1]+1，此时计算的g[i]是等于1的，所以此时g[i]=g[i-1]==0?0:g[i-1]+1

根据上面的分析总结图，推出g[i]的状态转移方程：

第一种情况：nums[i]>0时，此时g[i]=Math.max(0,g[i-1]==0?0:g[i-1]+1) ，可以简化成g[i]=g[i-1]==0?0:g[i-1]+1

第二种情况：nums[i]<0时，此时g[i]=Math.max(1,f[i-1]+1)，可以简化成f[i]=f[i-1]+1

3.初始化

这里依旧是选择多创建一部分空间实现初始化

根据一个表分析即可，此时用g表来分析，此时g[1]初始化有两种情况，当nums[0]<0时，要将g[1]初始化为1，所以根据g[i]状态转移方程小于0的情况，此时要将g[0]初始化为0，当nums[0]>0时，此时要将g[i]初始化为0，根据g[i]状态转移方程大于0的情况，此时要将f[0]初始化为0

第二个注意事项：注意下标的映射关系

4.填表顺序

从左往右同时填两个表即可

5.返回值

返回f表中的最大值

代码实现：

class Solution {public int getMaxLen(int[] nums) {int n=nums.length;int[] f=new int[n+1];int[] g=new int[n+1];f[0]=0;g[0]=0;int ret=Integer.MIN_VALUE;for(int i=1;i<n+1;i++){int x=nums[i-1];if(x>0){f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;}else if(x<0){f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;}ret=Math.max(ret,f[i]);}return ret;}
}

5.等差数列划分

题目链接：413. 等差数列划分 - 力扣（LeetCode） 

题目解析：返回nums数组中能够成等差数列的子数组的个数 

算法讲解：动态规划 

1.状态表示：经验+题目要求

由于题目要求返回nums数组中所有为等差数列的子数组的个数，此时就可以将状态表示：

dp[i]表示：以i位置元素为结尾的所有子数组中能构成等差数列的个数 

2.状态转移方程

首先要知道如果[a,b,c,d]这4个数构成等差数列，如果此时c,d,e也能构成等差数列，此时a.b,c,d,e也是能构成等差数列的

现在开始分析，因为构成等差数列至少需要3个元素，所以分析时要至少以3个元素开始分析，如下图

假设此时这3个元素是a，b，c，此时分析这三个数能否构成等差数列

第一种情况：如果a，b，c这3个数构成等差数列，也就是nums[i]-nums[i-1]==nums[i-1]-nums[i-1]，此时如果要求出dp[i]，首先就要知道以a，b为结尾的所有子数组中能构成等差数列的子数组个数，以a，b结尾就是以b结尾，此时就可以用dp[i-1]来表示以b结尾的所有子数组中能构成等差数列的个数，此时dp[i]就是在dp[i-1]的基础上加1即可，这里的加1是指dp[i-1]中没有包含a,b,c这种情况，如下图

第二种情况：a，b，c这三个元素不构成等差数列，如果a，b，c这三个元素不够成等差数列，那么此时a，b，c，d就也不会构成等差数列了，此时直接让dp[i]=0即可

3.初始化

因为构成等差数列至少需要3个数据，所以要将dp[0]和dp[1]都初始化为0

4.填表顺序

从左往右填表即可

5.返回值

因为要返回能构成等差数列的子数组个数，所以要用一个ret来记录

代码实现：

class Solution {public int numberOfArithmeticSlices(int[] nums) {int n=nums.length;if(n==1||n==2) return 0;int[] dp=new int[n];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;ret+=dp[i];}else{dp[i]=0;}}return ret;}
}

6.最长湍流子数组 

题目链接：978. 最长湍流子数组 - 力扣（LeetCode） 

题目解析：啥事湍流子数组呢？数组中的数据呈现下面的趋势就是湍流数组，如下图

算法讲解：动态规划

1.状态表示：经验+题目要求

首先想到的状态表示肯定是：

dp[i]表示：以i位置为结尾的所有子数组中，最长湍流子数组的长度

根据下面的分析，推出两个状态表示：

f[i]表示：以i位置为结尾的所有子数组中，最后呈现上升趋势状态下的最长湍流子数组的长度 

g[i]表示：以i位置为结尾的所有子数组中，最后呈现下降趋势状态下的最长湍流子数组的长度 

2.状态转移方程：

此时推算dp[i]时，由于找到子数组要是湍流子数组，所以此时nums[i-1]和nums[i]组成的趋势有上升和下降的两种情况，如下图

所以此时单独靠一个状态表示是不能够解决问题，还要添加两个状态表示f[i]和g[i] 

此时推算f[i]，依旧是上图的三种情况来分析f[i]

第一种情况：nums[i]>nums[i-1]

当nums[i]>nums[i-1]，最后一段是上升的趋势，由于要找的湍流子数组，所以此时首先要找出以i-1位置为结尾的所有子数组中，最后呈现下降趋势状态的最长湍流子数组的长度，根据g[i]的状态表示，可以用g[i-1]来表示，所以此时f[i]=g[i-1]+1

第二种情：nums[i]<nums[i-1]

当nums[i]<nums[i-1]，此时最后一段呈现下降趋势，不符合f[i]的状态表示，所以让nums[i]单独成为一个湍流子数组，则此时f[i]=1

第三种情况：nums[i]==nums[i-1]

当nums[i]==nums[i-1]，此时最后一段呈现没有变化的趋势，此时不符合f[i]的状态表示，所以让nums[i]单独成为一个湍流子数组，此时f[i]=1

接着来推算g[i]，还是上面这三种情况来分析

第一种情况：nums[i]>nums[i-1]

当nums[i]<nums[i-1]，最后一段是下降的趋势，由于要找的湍流子数组，所以此时首先要找出以i-1位置为结尾的所有子数组中，最后呈现上升趋势状态的最长湍流子数组的长度，根据f[i]的状态表示，可以用f[i-1]来表示，所以此时g[i]=f[i-1]+1

第二种情：nums[i]>nums[i-1]

当nums[i]>nums[i-1]，此时最后一段呈现上升趋势，不符合g[i]的状态表示，所以让nums[i]单独成为一个湍流子数组，则此时g[i]=1

第三种情况：nums[i]==nums[i-1]

当nums[i]==nums[i-1]，此时最后一段呈现没有变化的趋势，此时不符合g[i]的状态表示，所以让nums[i]单独成为一个湍流子数组，此时g[i]=1

3.初始化 

此时可以先将f表和g表都初始化为1，因为最坏的情况就是1，还有一个好处，就是写代码时就不用考虑f[i]和g[i]等于1的情况了

4.填表顺序

从左往右同时填两个表即可

5.返回值

返回f表和g表中的最大值

代码实现 

class Solution {public int maxTurbulenceSize(int[] nums) {int n=nums.length;int[] f=new int[n];int[] g=new int[n];for(int i=0;i<n;i++){f[i]=1;g[i]=1;}int ret=1;for(int i=1;i<n;i++){if(nums[i]>nums[i-1]){f[i]=g[i-1]+1;}else if(nums[i]<nums[i-1]){g[i]=f[i-1]+1;}ret=Math.max(ret,Math.max(f[i],g[i]));}return ret;}
}

7.单词拆分 

题目链接：139. 单词拆分 - 力扣（LeetCode） 

题目解析：判断字符串s能不能有字典中的字符串拼接出来，字典中的字符串可以重复使用

算法讲解：动态规划

1.状态表示：经验+题目要求

在这道题因为要判断字符串能不能由字典中的字符串拼接出来，可以这样定义状态表示：

dp[i]表示：[0，i]区间内的字符串，能否被字典中的字符串拼接而成

当dp[i]==true时，说明可以由字典中的字符串拼接而成

当dp[i]==false时，说明不可以由字典中的字符串拼接而成 

2.状态转移方程

根据最后一个单词的情况来分析问题，此时可以是字符串中的最后一个字符作为单独一个单词来作为最后一个单词，也可以是最后一个字符和前面的字符合并成为一个单词作为最后一个单词，如下图

此时，子字符串就可以分为两种情况了，也就是前面一个单词和最后一个单词，如下图

此时，要向判断dp[i]是true还是false，也就是判断能不能由字典中的字符串拼接而成，就需要判断前面一个单词能不能由字典中的字符串拼接而成，和最后一个单词存不存在于字典中，为了方便叙述，为了方便叙述，用一个变量j来表示最后一个单词的起始位置（此处的j是小于等于i且大于等于0的），要想则dp[j-1]就是[0，j-1]区间内的字符串能否由字典中的单词拼接而成，如果dp[j-1]==true且最后一个单词存在于字典中，则dp[i]就等于true，否则dp[i]就等于false，如下图

3.初始化

为了方便初始化，将创建虚拟节点来实现初始化，此时需要注意虚拟节点填的值要保证后面填表正确和下标映射的问题

下标映射这里，可以往s的前面加一个空格，就可以避免下标映射的问题了

4.填表顺序

从左往右填表即可

5.返回值

返回dp[n]即可

代码实现

为什么第二个循环里面是j>=1呢？因为前面往s前面增加了一个空格，让s的长度增加了1，所以此时的1就是原本的0 

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> hash=new HashSet<>(wordDict);int n=s.length();boolean[] dp=new boolean[n+1];dp[0]=true;s=" "+s;for(int i=1;i<n+1;i++){for(int j=i;j>=1;j--){if(dp[j-1]&&hash.contains(s.substring(j,i+1))){dp[i]=true;break;}}}return dp[n];}
}

8.环绕字符串中唯一的子字符串 

题目链接：467. 环绕字符串中唯一的子字符串 - 力扣（LeetCode） 

题目解析：计算并返回字符串s中有多少非空不同子串在base中出现

算法讲解：动态规划

1.状态表示：经验+题目要求

因为题目要求返回字符串s中有多少非空不同子串在base中出现，根据经验，可以这样定义状态表示：

dp[i]表示：以i位置元素结尾的非空不同子串中，有多少个在base中出现 

2.状态转移方程

因为我们要在字符串s中找子串，所以此时以i位置字符结尾的子串会有两种情况，分别是长度为1和长度大于1的情况，如下图

所以此时推算dp[i]时，也要分为两种情况：

第一种情况：子串的长度为1 

当子串为1时，也就是ch[i]单独一个字符作为子串，此时是一定会在base中出现的，所以此时dp[i]=1

第二种情况：子串的长度大于1

当子串的长度大于1时，如果要计算dp[i]，就要先知道以i-1位置为结尾的非空子串，有多少个出现在base中，根据dp[i]的状态表示，可以dp[i-1]来表示

那如何判断以i位置为结尾的非空子串是出现在base中的呢？

此时无非就两种情况，当ch[i]和ch[i-1]在26个小写的英文中是相邻的，也就是ch[i-1]+1=ch[i]，因为base是连续字符串，所以还要考虑ch[i-1]=='z'和ch[i]=='a'的情况，当这两种情况，有一种符合时，就代表在base中出现

3.初始化

此时可以先将dp表中的全部数据初始化为1，因为此时的最坏情况就是1，这样还有一个好处，就是写代码时，就不用考虑dp[i]==1的情况了

4.填表顺序

从左往右填dp表即可

5.返回值

注意返回时是要求不同子串的个数，所以还要去重

以s="aca"为例，当i等于0时，此时子串就是"a"，此时dp[0]=1，当i等于3时，此时子串的情况就有"a"，"ca"，和"aca"的情况，此时计算dp[3]时，有计算了一次子串为"a"的情况，所以此时要去重

去重策略：

根据上面的分析，"aca"的情况就已经包含了"a"的情况，所以在计算ret时，相同字符结尾的dp值，去最大的那一个即可

如何实现去重策略：

定义一个大小为26的int数组，遍历dp表，将相同字符结尾的dp值中较大的放进数组即可

代码实现：

class Solution {public int findSubstringInWraproundString(String s) {char[] ch=s.toCharArray();int n=ch.length;int[] dp=new int[n];for(int i=0;i<n;i++) dp[i]=1;for(int i=1;i<n;i++){if(ch[i-1]+1==ch[i] || ch[i-1]=='z'&&ch[i]=='a'){dp[i]+=dp[i-1];}}//去重int[] hash=new int[26];for(int i=0;i<n;i++)hash[ch[i]-'a']=Math.max(hash[ch[i]-'a'],dp[i]);//计算返回结果int ret=0;for(int i=0;i<26;i++)ret+=hash[i];return ret;}
}