无训练视频异常检测：基于对比事件裁决的原理与实践
2026/9/2 15:40:33
子数组问题
- 最大子数组和
- 环形子数组的最大和
- 乘积最大的子数组
- 乘积为正数的最长子数组长度
- 等差数列划分
- 单词拆分
- 环绕字符串中唯一的子字符串
最大子数组和
题目解析：找出数组中和最大的子数组，并返回最大和
动态规划
状态表示：dp[i]表示以i位置为结尾的最大子数组和
状态转移方程：dp[i] = Math.max(nums[i ], dp[i - 1] + nums[i ]);
初始化：dp[0] = 0 或者引入一个虚拟位置，dp从1下标开始
填表顺序：从左到右
返回值：dp表中的最大值
classSolution{publicintmaxSubArray(int[]nums){intn=nums.length;int[]dp=newint[n+1];dp[0]=0;intret=-Integer.MIN_VALUE;for(inti=1;i<=n;i++){dp[i]=Math.max(nums[i-1],dp[i-1]+nums[i-1]);ret=Math.max(ret,dp[i]);}returnret;}}环形子数组的最大和
题目解析：找出数组中的连续子数组的最大和，并返回最大和，数组是环形(首尾相连)，将其分为两种情况
1和上题不是环形的一样，正常找出的连续子数组的最大和
2.利用了环形性质，找出连续子数组的最小和，sum-min就是其对应最大和
动态规划
状态表示：
f[i]表示以i位置为结尾的最大子数组和
g[i]表示以i位置为结尾的最小子数组和
状态转移方程：
f[i] = Math.max(nums[i ], f[i - 1] + nums[i ]);
g[i] = Math.max(nums[i ], g[i - 1] + nums[i ]);
初始化：
f[0] = g[0] = nums[0]
或者引入虚拟节点f[0] = g[0] = 0,此时与nums数组下标对应关系有所改变
填表顺序：从左到右
返回值：Math.max(fmax,sum - gmin)
//不使用虚拟节点classSolution{publicintmaxSubarraySumCircular(int[]nums){intn=nums.length;intsum=0;intfmax=Integer.MIN_VALUE;intgmin=Integer.MAX_VALUE;int[]f=newint[n];//最大值int[]g=newint[n];//最小值//初始化f[0]=g[0]=nums[0];sum+=nums[0];fmax=Math.max(fmax,f[0]);gmin=Math.min(gmin,g[0]);for(inti=1;i<n;i++){f[i]=Math.max(nums[i],f[i-1]+nums[i]);g[i]=Math.min(nums[i],g[i-1]+nums[i]);sum+=nums[i];fmax=Math.max(fmax,f[i]);gmin=Math.min(gmin,g[i]);}//可能数组全是负数，这样直接返回fmax即可returngmin==sum?fmax:Math.max(fmax,sum-gmin);}}classSolution{publicintmaxSubarraySumCircular(int[]nums){intn=nums.length;intsum=0;intfmax=Integer.MIN_VALUE;intgmin=Integer.MAX_VALUE;int[]f=newint[n+1];//最大值int[]g=newint[n+1];//最小值for(inti=1;i<=n;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]);sum+=nums[i-1];fmax=Math.max(fmax,f[i]);gmin=Math.min(gmin,g[i]);}//可能数组全是负数，这样直接返回fmax即可returngmin==sum?fmax:Math.max(fmax,sum-gmin);}}乘积最大的子数组
题目解析：找出数组中最大连续子数组积
数组中是有负数的，使用一个dp表表示以i位置为结尾的最大子数组积是不够的，因为负负得正，当前数是一个负数，从前面找一个最小的子数组积，此时才是最大的
动态规划
状态表示：
f[i]表示以i位置为结尾的最大连续子数组积
g[i]表示以i位置为结尾的最小连续子数组积
状态转移方程：
f[i] = max(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i])
g[i] = min(nums[i] , f[i-1] * nums[i] , g[i-1] * nums[i])
初始化：
引入虚拟节点f[0] = g[0] = 1,此时与nums数组下标对应关系有所改变
填表顺序：从左到右
返回值：f表中的最大值
classSolution{publicintmaxProduct(int[]nums){intn=nums.length;int[]f=newint[n+1];int[]g=newint[n+1];f[0]=g[0]=1;intret=Integer.MIN_VALUE;for(inti=1;i<=n;i++){intx=nums[i-1];inty=f[i-1]*nums[i-1];intz=g[i-1]*nums[i-1];f[i]=Math.max(Math.max(x,y),z);g[i]=Math.min(Math.min(x,y),z);ret=Math.max(f[i],ret);}returnret;}}乘积为正数的最长子数组长度
题目解析：乘积为正的连续子数组最长长度
动态规划
状态表示：
f[i]表示以i位置为结尾的乘积为正的最长子数组长度
g[i]表示以i位置为结尾的乘积为负的最长子数组长度
状态转移方程：
nums[i] > 0f[i] = f[i-1] + 1; g[i] = g[i-1] == 0 ? 0 : g[i-1] + 1;
nums[i] < 0f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1; g[i] = f[i-1] + 1;
初始化：
引入虚拟节点f[0] = g[0] = 1,此时与nums数组下标对应关系有所改变
填表顺序：从左到右
返回值：f表中的最大值
classSolution{publicintgetMaxLen(int[]nums){intn=nums.length;int[]f=newint[n+1];int[]g=newint[n+1];intret=Integer.MIN_VALUE;for(inti=1;i<=n;i++){if(nums[i-1]>0){f[i]=f[i-1]+1;g[i]=g[i-1]==0?0:g[i-1]+1;}elseif(nums[i-1]<0){f[i]=g[i-1]==0?0:g[i-1]+1;g[i]=f[i-1]+1;}ret=Math.max(ret,f[i]);}returnret;}}等差数列划分
题目解析：求出一个数组中连续子数组可以构成等差数列的个数
动态规划
状态表示：
dp[i]：以i位置结尾的连续子数组为等差数列的个数
状态转移方程：
dp[i] = nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ? dp[i-1] + 1 : 0;
初始化：
dp[0] = dp[1] = 0
填表顺序：从左到右
返回值：f表中总和
classSolution{publicintnumberOfArithmeticSlices(int[]nums){intret=0;intn=nums.length;int[]dp=newint[n];for(inti=2;i<n;i++){dp[i]=nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;ret+=dp[i];}returnret;}}题目解析：求连续湍流子数组的最长长度
动态规划
状态表示：
f[i]表示以i位置为结尾的最后呈现"上升"趋势最长湍流子数组长度
g[i]表示以i位置为结尾的最后呈现"下降"趋势最长湍流子数组长度
状态转移方程：
f[i] = g[i] = 1
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;
}
初始化：
可以将所有f表和g表全部初始为1
填表顺序：从左到右
返回值：f和g表中最大值
classSolution{publicintmaxTurbulenceSize(int[]arr){intn=arr.length;int[]f=newint[n];int[]g=newint[n];//因为这里最小是1，可以将f表和g表全部初始化为1for(inti=0;i<n;i++){f[i]=g[i]=1;}intret=1;for(inti=1;i<n;i++){if(arr[i]>arr[i-1]){f[i]=g[i-1]+1;}elseif(arr[i]<arr[i-1]){g[i]=f[i-1]+1;}ret=Math.max(Math.max(f[i],g[i]),ret);}returnret;}}//不将其全部初始为1//进入循环，可以先将其初始化为1，符合湍流条件进行更新classSolution{publicintmaxTurbulenceSize(int[]arr){intn=arr.length;int[]f=newint[n];int[]g=newint[n];intret=1;f[0]=g[0]=1;for(inti=1;i<n;i++){//不符合表的特征，为1f[i]=g[i]=1;if(arr[i]>arr[i-1]){f[i]=g[i-1]+1;}elseif(arr[i]<arr[i-1]){g[i]=f[i-1]+1;}ret=Math.max(Math.max(f[i],g[i]),ret);}returnret;}}单词拆分
题目解析：给一个s字符串和一个字典，判断利用字典中的单词是否可以拼接处s这个字符串(字典中单词可以重复使用)
动态规划
状态表示：
布尔类型
dp[i]：s字符串[0,i]区间是否可以使用字典中单词拼接而成
状态转移方程：
判断[0,i]区间字符串是否可以被拼接而成，可以将其分为两部分[0,j-1]和[j,i]
j的取值范围[0,i]
条件1 ：[0,j-1] - > dp[j-1]
条件2：[j,i] - > 判断s字符串中是否存在这个单词
当条件1和2都满足，此时dp[i]是true，如果所有情况都不满足返回false
初始化：
引入一个虚拟节点 dp[0] = true
填表顺序：从左到右
返回值：dp[i]
细节优化 优化1：可以使用一个哈希表将字典中单词放入，方便查找一个单词是否在字典中 优化2：dp表引入了虚拟节点，下标对应关系和s字符串有所改变 可以让s=" "+s将字符串s向后移动一个位置,这样下标就一一对应classSolution{publicbooleanwordBreak(Strings,List<String>wordDict){Set<String>hash=newHashSet<>(wordDict);intn=s.length();boolean[]dp=newboolean[n+1];s=" "+s;//方便处理下标映射关系dp[0]=true;for(inti=1;i<=n;i++){for(intj=i;j>=1;j--){//[1,j-1] -> dp[j-1]为true//&& [j,i]存在字典中if(dp[j-1]&&hash.contains(s.substring(j,i+1))){dp[i]=true;break;}}}returndp[n];}}环绕字符串中唯一的子字符串
题目解析：有一个base字符串，其是abcdef…………xyzabce……26个小写字母无限环绕的字符串，给了一个字符串s,求s中有多少不同的子串在base出现
动态规划
状态表示
dp[i] : 以i位置的元素结尾的，有多少子串存在base中
状态转移方程
dp[i]的值为以i元素结尾子串长度为1 + 子串长度>1之和
dp[i] = 1 + dp[i-1]（前提是s[i-1] 和 s[i]是连续的）
初始化
可以将dp表中都现初始化为1，因为其长度为1都是在base中的，此时这里状态转移方程变成 dp[i] += dp[i-1]（满足条件才进行相加）
填表顺序
从左到右
返回值
不可以直接返回dp表所有值之和，因为有重复
因为以同一字符结尾dp值，肯定更长的dp值更大，并且其是包含相同结尾较短字符中的所有情况，所以此时直接返回所有字符结尾中dp表中最大值
此时可以使用一个26数组统计对应以某个字符结尾的最大结果即可
classSolution{publicintfindSubstringInWraproundString(Stringss){char[]s=ss.toCharArray();intn=ss.length();int[]hash=newint[26];//以这个字符结尾有多少子串在环绕字符串中int[]dp=newint[n];//此时这里都是由小写字母组成，单个字符肯定符合for(inti=0;i<n;i++){dp[i]=1;}hash[s[0]-'a']=1;for(inti=1;i<n;i++){if(s[i-1]+1==s[i]||(s[i-1]=='z'&&s[i]=='a')){dp[i]+=dp[i-1];}//更新哈希表(去重)hash[s[i]-'a']=Math.max(dp[i],hash[s[i]-'a']);}intret=0;for(inti=0;i<26;i++){ret+=hash[i];}returnret;}}