lc1458
两个序列dp 移动i j
二维dp: dp[i][j] 表示 nums1 前i个元素和 nums2 前j个元素的最大点积
“不取nums1当前元素、不取nums2当前元素、取两者当前元素（累加或单独取）”四种转移取最大值，最终得到两个数组子序列的最大点积
class Solution {
public:
int maxDotProduct(vector<int>& nums1, vector<int>& nums2)
{
int m=nums1.size(),n=nums2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,-0x3f3f3f3f));//找最大 自身要初始化最小
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
//四种转移取最大
dp[i][j]=max(dp[i][j-1],max(dp[i-1][j-1]+nums1[i-1]*nums2[j-1],dp[i-1][j]));
dp[i][j]=max(dp[i][j],nums1[i-1]*nums2[j-1]);
}
}
return dp[m][n];
}
};
二分+滑窗
先对数组排序，二分猜答案:可能的中位数
滑窗统计“长度≥m的子数组中，中位数≥当前枚举值”的可行性（即子数组中≥该值的元素数≥中位数位置所需数量），最终找到最大的可行中位数。
lc2565
前后缀分解+预存最长子序列
ans = min(ans, (int)t.size() - a - b);
前缀数组记录s前i位能匹配t的最长前缀
后缀数组记录s后i位能匹配t的最长后缀
遍历合并两侧匹配长度，取t未被匹配的最短长度即答案
/*
令 left 为删除字符中的最小下标。
令 right 为删除字符中的最大下标。
字符串的得分为 right - left + 1 。
尽可能长的 连续保留拼接 t左右
*/
class Solution {
public:
int minimumScore(string s, string t) {
int n = s.size();
vector<int> l(n,0), r(n,0);
int p = 0;
for (int i = 0; i < s.size(); i++)
{
if (p<t.size()&&s[i] == t[p])
p++;
l[i] = p;
}
p = t.size() - 1;
for (int i = s.size() - 1; i >= 0; i--)
{
if (p >= 0 && s[i] == t[p])
p--;
r[i] = t.size() - 1 - p;
}
int ans = 1e9;
for (int i = 0; i < n-1; i++)
{
int a = l[i], b = r[i + 1];
if (a + b >= t.size())
return 0;
ans = min(ans, (int)t.size() - a - b);
}
ans = min(ans, (int)t.size()-r[0]);
ans = min(ans, (int)t.size()-l[n - 1]);
return ans;
}
};
