数组先减去数组元素的最小值,必然会出现有些元素为0的情况;
以这些0为界限的区间再次重复操作,可以想到用递归来做;
C++ 代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int N=1e5+10;
int a[N];
int get(int l,int r)
{
if(l==r) return a[l];//区间只有一个数,返回数的值;
else if(l>r) return 0;
int m=10000,res=0;
for(int i=l;i<=r;i++)
m=min(m,a[i]);//区间的最小值;
res+=m;//结果加上最小值;
for(int i=l;i<=r;i++)
{
a[i]-=m;//每次减少m;
if(!a[i])
{
res+=get(l,i-1);//递归不为0的区间;
l=i+1;//更新l;
}
}
//上面的循环并不会计算a[r]-m不为0的情况;
if(a[r]!=0) res+=get(l,r);//右区间不为0时,需要加上最后一个区间;
return res;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
cout<<get(0,n-1)<<endl;
return 0;
}
不错,但是这样做的时间复杂度最坏是N*最大深度(升序)。