题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
DP:
l:前i个数,以当前第i位数为最大值的最大值和为多少
转移
找到比当前数小的第一个数x
l[i]=l[x]+(i-x)*a[i]
因为x+1到i-1的数都是大于a[i]的,但是要以a[i]为最大值,只能把这一段全变成a[i]
因为保证了l[x]是,以当前第x位数为最大值的最大值和,且a[i]>=a[x],所以前面的x个数保证也小于等于a[i]
时间复杂度
参考文献
C++ 代码
class Solution {
public:
long long maximumSumOfHeights(vector<int>& maxHeights) {
int n=maxHeights.size();
maxHeights.insert(maxHeights.begin(),0);
vector<long long> l(n+10,0),r(n+10,0);
maxHeights.push_back(0);
//3 2 3 4 3
vector<int> st;
for(int i=1;i<=n;i++)
{
while(st.size()&&maxHeights[i]<maxHeights[st.back()]) st.pop_back();
if(maxHeights[i]>=maxHeights[i-1]) l[i]=l[i-1]+maxHeights[i];
else{
if(st.size()==0){
l[i]=1ll*i*maxHeights[i];
}
else{
l[i]=l[st.back()]+1ll*maxHeights[i]*(i-st.back());
}
}
st.push_back(i);
}
st.clear();
for(int i=n;i>=1;i--){
while(st.size()&&maxHeights[i]<maxHeights[st.back()]) st.pop_back();
if(maxHeights[i]>=maxHeights[i+1]) r[i]=r[i+1]+maxHeights[i];
else{
if(st.size()==0)
{
r[i]=1ll*(n-i+1)*maxHeights[i];
}
else{
r[i]=r[st.back()]+1ll*maxHeights[i]*(st.back()-i);
}
}
st.push_back(i);
}
long long res=0;
for(int i=1;i<=n;i++) res=max(res,1ll*l[i]+r[i]-maxHeights[i]);
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
tql