一.前言

这是一种典型的线性动态规划类型，这种题型的题目通常的朴素方法是两层循环暴力解决，但第二维可以使用单调队列或单调栈来对算法的时间复杂度进行优化

二.算法分析

1.例题讲解

例题1

朴素算法的主循环保持不变，对第二层循环进行优化。可以看出：如果下标大的点，值也比前面的值大，那么其前面的数就没有存在的必要，即没有dp的意义。我们用一个栈存储有dp意义的点，根据前面的分析，这个栈显然是单调递减的。而若再次出现下标大的点，值也比前面的值大，则将该栈顶中无意义的点依次排除。

#include<bits/stdc++.h>
using namespace std;

long long a[1000005],stk[1000005],top;

int main(){
	long long n,ans=-1e9;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=top;j++)ans=max(ans,(stk[j]+i)*min(a[stk[j]],a[i]));
		ans=max(ans,a[i]*i);
		while(a[i]>=a[stk[top]]&&top!=0)top--;//将无意义的点依次丢弃 
		stk[++top]=i; 
	}
	cout<<ans;
	return 0;
} 

仍然超时
能否再优化一下这个单调栈呢？？？

在对第i个点处理时，在单调栈中的值比第i个点值大的点中，下标最大的点最优，而其他点在与第i个点的配对过程中，暂时没有dp的必要，因为min(stk[j],a[i])

#include<bits/stdc++.h>
using namespace std;

long long a[10000005],stk[10000005],top;

int main(){
	long long n,ans=-1e9;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	for(int i=1;i<=n;i++){
		ans=max(ans,a[i]*i);
		while(a[i]>=a[stk[top]]&&top!=0){//将无意义的点依次丢弃
			ans=max(ans,(stk[top]+i)*a[stk[top]]);//更新最优结果 
			top--;
		}
		ans=max(ans,(i+stk[top])*a[i]);//在值大于a[i]的点中，只有下标最大的点有dp的必要 
		stk[++top]=i;
	}
	cout<<ans;
	return 0;
} 

在数据加强版中，仍然超时