目录
一，3411. 最长乘积等价子数组
二，3412. 计算字符串的镜像分数
三，3413. 收集连续 K 个袋子可以获得的最多硬币数量
四，3414. 不重叠区间的最大得分
一，3411. 最长乘积等价子数组
本题数据范围小，直接暴力枚举，代码如下：
class Solution {public int maxLength(int[] nums) {int n = nums.length;int ans = 0;for(int l=0; l<n; l++){for(int r=l; r<n; r++){int p = 1, g = 0, lc = 1;for(int i=l; i<=r; i++){p *= nums[i];g = gcd(nums[i], g);lc = lcm(nums[i], lc);}if(p == g * lc) ans = Math.max(ans, r-l+1);}}return ans;}int gcd(int a, int b){return b==0?a:gcd(b,a%b);}int lcm(int a, int b){return a*b/gcd(a,b);}
}二，3412. 计算字符串的镜像分数
本题就是要存储26个字母的出现的所有下标，对于 s[i] 来说，需要找到相应镜像的字母 c，然后返回字母 c 最近的下标，也就是说，需要一个先进后出的数据结构——栈来存储 26 个字母的下标，代码如下：
class Solution {public long calculateScore(String s) {Stack<Integer>[] st = new Stack[26];Arrays.setAll(st, e->new Stack<>());long ans = 0;for(int i=0; i<s.length(); i++){int c = s.charAt(i) - 'a';if(!st[25-c].isEmpty()){ans += i - st[25-c].pop();}else{st[c].push(i);}}return ans;}
}三，3413. 收集连续 K 个袋子可以获得的最多硬币数量
本题求连续 k 个袋子可获得的最多硬币数量，就是维护一个长度为 k 的滑动窗口，关键的问题就变成了如何维护窗口的更新（进/出），求最多，贪心的想对于一个区间 [L，R]，需要尽可能多的包含这个区间，那么有两种情况——以 L 为左端点，向右维护一个长为 k 的窗口；以 R 为右端点，向左维护一个长为 k 的窗口。需要分别求出上述两种情况，取最大值。
这里写以 L 为左端点，向右维护一个长为 k 的窗口的维护方法，另一种可以通过镜像的方式，复用此代码。如图所示：
代码如下：
class Solution {long window(int[][] f, int k){int n = f.length;long ans = 0;long cover = 0, uncover = 0;for(int i=0, j=0; i<n; i++){long l = f[i][0], r = f[i][1], c = f[i][2];cover += (r - l + 1) * c;while(f[j][1] < r - k + 1){cover -= (long)(f[j][1] - f[j][0] + 1) * f[j][2];j++;}uncover = Math.max((long)(r - k + 1 - f[j][0]) * f[j][2], 0) ;ans = Math.max(ans, cover - uncover);}return ans;}public long maximumCoins(int[][] coins, int k) {Arrays.sort(coins, (x, y) -> x[0] - y[0]);long ans = window(coins, k);for(int[] c : coins){int t = -c[0];c[0] = -c[1];c[1] = t;}int n = coins.length;for(int i=0; i<n/2; i++){int[] t = coins[i];coins[i] = coins[n-1-i];coins[n-1-i] = t;}return Math.max(ans, window(coins, k));}
}四，3414. 不重叠区间的最大得分
定义f[i][j]: 在前 i 个区间选出 j 个不重叠区间的最大得分和此时字典序最小的区间下标顺序。标准的0-1背包做法，难点在于维护字典序最小的区间下标顺序。
代码如下：
class Solution {private record Tuple(long w, List<Integer> id){}private record Info(int l, int r, int w, int i){}public int[] maximumWeight(List<List<Integer>> intervals) {int n = intervals.size();Info[] t = new Info[n];for(int i=0; i<n; i++){List<Integer> x = intervals.get(i);int l = x.get(0), r = x.get(1), w = x.get(2);t[i] = new Info(l, r, w, i);}Arrays.sort(t, (x, y) -> x.r - y.r);Tuple[][] f = new Tuple[n+1][5];Arrays.setAll(f[0], e->new Tuple(0, new ArrayList<>()));for(int i=0; i<n; i++){int l = t[i].l, r = t[i].r, w = t[i].w;int k = search(t, l-1, i);f[i+1][0] = new Tuple(0, new ArrayList<>());for(int j=1; j<5; j++){long s1 = f[i][j].w;long s2 = f[k+1][j-1].w + w;if(s1 > s2){f[i+1][j] = f[i][j];continue;}List<Integer> tmp = new ArrayList<>(f[k+1][j-1].id);tmp.add(t[i].i);Collections.sort(tmp);if(s1 == s2 && compareLists(tmp, f[i][j].id) > 0){tmp = f[i][j].id;}f[i+1][j] = new Tuple(s2, tmp);}}return f[n][4].id.stream().mapToInt(v->v).toArray();}int compareLists(List<Integer> a, List<Integer> b){for(int i=0; i<Math.min(a.size(), b.size()); i++){if(!a.get(i).equals(b.get(i)))return a.get(i) - b.get(i);}return a.size() - b.size();}int search(Info[] t, int k, int r){int l = 0;while(l <= r){int mid = (l + r) >>> 1;if(t[mid].r <= k){l = mid + 1;}else{r = mid - 1;}}return l - 1;}
}
