在 C++ 中，在 [L, R] 范围内的最多 K 次移动中最大化数字的总和
我们得到一个包含整数的数组Arr[]和包含查询的二维数组Q。每个查询包含3个值，分别是lpos、rpos和K。一个可以在一个步骤中从索引i移动到下一个索引i+1或保留在该索引中。最多只能以K步从lpos移动到rpos。在每一步添加所有数字，包括最左边的数字。目标是在最大K次移动中最大化总和。如果在K步中不可能从lpos移动到rpos，则打印“No”。让我们了解更多。
让我们看看这个的各种输入输出场景-
在 -Arr[]={1,2,4,-1};
Q[][3]={{0,2,2},{0,2,1},{3,3,1},{0,2,3}};
出 -
查询1：7
查询2：否
查询3：否
查询4：11
说明 -
第一个查询：-
我们可以在最多2个步骤中从索引0移动到2：-
步骤1:-索引0到1(1+2=3)
第2步：-索引1到2(3+4=7)
第二个问题：-
我们不能在最大1步中从索引0移动到2。打印“否”
第三个查询：-
我们不能在最大1步中从索引3移动到3。打印“否”
第四个问题：-
我们可以在最多3个步骤中从索引0移动到2：-
步骤1:-索引0到1(1+2=3)
第2步：-索引1到2(3+4=7)
第3步：-保持索引2(7+4=11)
在 -Arr[]={1,2,3,3,2};Q[][3]={{0,3,2},{1,4,3}};
出 -
查询1：否
查询2：10
说明 -
第一个查询：-
我们不能在最大1步中从索引0移动到2。打印“否”
第二个问题：-
我们可以最多分3个步骤从索引1移动到4：-
第1步：-索引1到2(2+3=5)
第2步：-索引2到3(5+3=8)
第3步：-索引3到4(8+2=10)
下面程序中使用的方法如下
在这种方法中，我们将使用lpos到rpos范围的段树来找到可能的最大值并使用前缀和计算所有数字的总和。
取输入数组Arr[]和查询矩阵Q[][]。
以sgTreee[5*length]为数组实现段树。
取pSum[length]作为前缀和数组。
函数createTree(intmin,intmax,intpos,intsgT[],intarr[],intlen)用于在段树中创建值。
检查是否(min==max)这意味着它是一个叶节点。设置sgT[pos]=arr[max]。
取midd=(min+max)/2。
为左右子树调用createTree(min,midd,loc1,sgT,arr,len)和createTree(midd+1,max,loc2,sgT,arr,len)以获取左右子树，其中loc1=2*pos+1和loc2=2*位置+2。
取tmp1=sgT[loc1]和tmp2=sgT[loc2]并用tmp1或tmp2中的最大值更新sgT[pos]。
函数preSum(intpSum4[],intarr4[],intlen4)获取输入数组并使用for循环更新前缀数组。
对于从索引1到最后一个的每个元素，更新pSum4[j]=pSum4[j-1]+arr4[j];
函数resQuery(intlen3,intarr3[],intsgT3[],intpSum3[],intq1[][3],intqlen1)接受所有输入参数并打印每个查询的结果。
在里面resQuery()，调用solQuery(intlpos,intrpos,intk,intlen2,intarr2[],intsgT2[],intpSum2[])使用for循环对每个查询一一求解。
函数solQuery(intlpos,intrpos,intk,intlen2,intarr2[],intsgT2[],intpSum2[])求解查询并返回结果。
如果rpos-lpos>k则返回-1，因为不可能有解决方案。
取maxVal=findMax(0,len2-1,lpos,rpos,0,sgT2,arr2,len2);
如果maxVal<0，则将maxVal设置为0
取变量sum=pSum2[rpos]。
如果lpos>0则设置sum-=pSum2[lpos-1]并且result=sum+(k-(rpos-lpos))*maxVal。
返回结果。
函数findMax(intstart,intend,intmin1,intmax1,intpos1,intsgT1[],intarr1[],intlen1)返回范围lpos和rpos之间的最大值。
如果(min1<=start)和(max1>=end)则返回sgT1[pos1]因为存在重叠。
如果(end<min1||start>max1)则发生超出范围，因此返回INT_MIN。
使用递归调用左子树和右子树计算lmax和rmax并返回两个最大值。
最后，将为每个查询打印结果。如果没有解决方案，则为“否”
示例
#include <bits/stdc++.h>
using namespace std;
void createTree(int min, int max, int pos,
int sgT[], int arr[], int len){ if (min == max) {
sgT[pos] = arr[max];
return;
}
int midd = (min + max) / 2;
int loc1=2*pos+1;
int loc2=2*pos+2;
createTree(min, midd, loc1, sgT, arr, len);
createTree(midd + 1, max, loc2, sgT, arr, len);
int tmp1=sgT[loc1];
int tmp2=sgT[loc2];
sgT[pos] = tmp1>tmp2 ? tmp1 : tmp2 ;
}
int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1){
int middle;
if (min1 <= start)
{ if( max1 >= end){
return sgT1[pos1];
}
}
if (end < min1 || start > max1)
{ return INT_MIN; }
middle = (start + end) / 2;
int loc1=2 * pos1 + 1;
int loc2=2 * pos1 + 2;
int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
int rmax = findMax(middle + 1, end, min1, max1, loc2, sgT1, arr1, len1);
int res=lmax>rmax?lmax:rmax;
return res;
}
int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]){
int result;
if (rpos - lpos > k)
{ return -1; }
int maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
if (maxVal < 0)
{ maxVal = 0; }
int sum = pSum2[rpos];
if (lpos > 0)
{ sum -= pSum2[lpos - 1]; }
result = sum + (k - (rpos - lpos)) * maxVal;
return result;
}
void resQuery(int len3, int arr3[], int sgT3[],
int pSum3[], int q1[][3], int qlen1){
int i;
int result;
for (i = 0; i < qlen1; i++) {
result = solQuery(q1[i][0], q1[i][1],q1[i][2], len3, arr3, sgT3, pSum3);
if (result == -1)
{ cout <<endl<<"Query "<<i+1<<": "<<"NO"; }
else
{ cout <<endl<<"Query "<<i+1<<": "<<result; }
}
}
void preSum(int pSum4[], int arr4[], int len4){
pSum4[0] = arr4[0];
int j;
for (j = 1; j < len4; j++){
pSum4[j] = pSum4[j - 1] + arr4[j];
}
}
int main(){
int Arr[] = {1, 2, 4, -1 };
int length = sizeof(Arr) / sizeof(Arr[0]);
int sgTreee[5 * length];
createTree(0, length - 1, 0, sgTreee, Arr, length);
int pSum[length];
preSum(pSum, Arr, length);
int Q[][3] = { { 0, 2, 2 },
{ 0, 2, 1 },
{ 3, 3, 1 },
{ 0, 2, 3} };
int qlen = sizeof(Q) / sizeof(Q[0]);
resQuery(length, Arr, sgTreee, pSum, Q, qlen);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
Query 1: 7 Query 2: NO Query 3: NO Query 4: 11