力扣 — — 2555. 两个线段获得的最多奖品
一、题目描述
题目大意：给定一个数组prizePositions，数组中的值表示的是奖品的位置，每一个位置可以有多个奖品，并且设定一个线段的长度 K K K，要求从所有奖品位置中选择两个长度为 K K K 的连续位置线段，并且要求这两个线段中的奖品位置上的奖品数量之和是最大的。（假设：数组prizePositions是一个非递减的序列）
二、问题分析
通过分析问题，由贪心的思想可以想到，不重叠的两个线段一定会比重叠的两个线段包含的奖品数量多，由此可以使用滑动窗口和动态规划算法进行求解，具体求解为如下：
- 将数组分割为两个部分，从前往后遍历每一个分割的位置。
- 对于每一个位置，都可以将原数组分割为两个部分，由此，我们可以求得前一个部分的最大值和后一个位置的最大值，将这两个位置的最大值进行相加即可得到最后的一个整体的大值。
- 对于上述方法，我们可以使用动态规划的方法进行求解，分为从前向后遍历以及从后向前遍历，在每一次遍历的过程中，求每一个位置滑动窗口的最大值，这里可以使用两个数组分别进行记录。
- 最后遍历每一个分割的位置（即：利用两个动态数组进行求解），将前一个部分的最大值与后一个位置的最大值进行相加，寻求一个全局的最大值，该最大值即为最终要求的最大值。
三、代码实现
详细代码
int myUnite(vector<int>& prizePositions, int k){int n = prizePositions.size();// 设定两个数组，分别存储从前向后遍历的动态最大值和从后向前的动态最大值。vector<int> perArray(n + 1), backArray(n + 1);// 将数组分割为两个部分， 求前一个部分for(int i = 0, j = 0; j < n; j ++){// 用于控制窗口的大小，避免窗口大于给定的值。while((prizePositions[j] - prizePositions[i]) > k) {i ++;}// 对于每一个位置，都进行动态决策perArray[j + 1] = max(perArray[j], j - i + 1);}// 先对数组进行反转reverse(prizePositions.begin(), prizePositions.end());// 将数组分割为两个部分，求后一个部分for(int i = 0, j = 0; j < n; j ++){// 控制窗口大小, 进行反转之后，后一个值小于前一个值，所以使用前一个值减去后一个值。while((prizePositions[i] - prizePositions[j]) > k){i ++;}// 对每一个位置进行决策backArray[j + 1] = max(backArray[j], j - i + 1);}// 遍历每一个分割位置，求得全局的最优值int ans = 0;for(int i = 0; i <= n;i ++){ans = max(ans, perArray[i] + backArray[n - i]);}return ans;}
简化之后的代码：
class Solution {
public:int maximizeWin(vector<int>& prizePositions, int k){int n = prizePositions.size();// 使用匿名函数auto calc = [&] (vector<int>& prefix, int reverseFlag){// 遍历每一个位置寻找固定内的窗口的最大值for(int i = 0, j = 0; j < n; j++){// 控制窗口大小while(reverseFlag * (prizePositions[j] - prizePositions[i]) > k) {i++;}// 通过动态规划的思想，求当到当前位置为止，累计求得的最大值。prefix[j + 1] = max(prefix[j], j - i + 1);}};// 分别从前向后动态求值，在从后向前动态求值。vector<int> prefix(n + 1), backfix(n + 1);calc(prefix, 1);reverse(prizePositions.begin(), prizePositions.end());calc(backfix, -1);int ans = 0;for(int i = 0; i <= n;i ++){ans = max(ans, prefix[i] + backfix[n - i]);}return ans;}
};
