我正在做一个问题,其中需要找到段中最大元素的总和 - 段中最小元素的总和。我尝试使用稀疏表,但时间限制慢了两个。所以我做了类似的事情这个:
如果n=4
段是[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
. 该问题类似于 RMQ 问题,但我必须对所有段进行此操作并找到
sum=max(a[1],a[2])+
max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+max(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])
for(i=1;i<n;i++)
{
maxtilli[i-1]=INT_MIN;
mintilli[i-1]=INT_MAX;
for(k=1,j=i;j<=n;k++,j++)
{
if(a[j]>maxtilli[k-1])
{
maxtilli[k]=a[j];
}
else
{
maxtilli[k]=maxtilli[k-1];
}
if(a[j]<mintilli[k-1])
{
mintilli[k]=a[j];
}
else
{
mintilli[k]=mintilli[k-1];
}
if(i!=j)
{
ans+=(maxtilli[k]-mintilli[k]);
}
}
}
这里n
是 100,000 的数量级。那么有没有办法优化呢。
假设n=4
段是[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
。
需要的东西是
sum=max(a[1],a[2])+max(a[1],a[2],a[3])+max(a[1],a[2],a[3],a[4])+max(a[2],a[3])+max(a[2],a[3],a[4])+max(a[3],a[4])-min(a[1],a[2])+min(a[1],a[2],a[3])+min(a[1],a[2],a[3],a[4])+min(a[2],a[3])+min(a[2],a[3],a[4])+min(a[3],a[4])