枚举法:
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
typedef long long ll;
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
int t[n];
int m[n];
int k=0,l=0,y,i,j;
for(i=0;i<n;i++){
int flag=0;
int in1=1e4+10;
int in2=1e4+10;
int ax1=0;
int ax2=0;
for(j=i;j<n-1;j++){
in1=min(in1,a[j]);
in2=min(in1,a[j+1]);
if(in1==in2){
t[k++]=in1;
flag=1;
//cout<<"in1"<<in1<<' ';
break;
}
}
if(flag==1){
for(y=j;y<n-1;y++){
ax1=max(ax2,a[y]);
ax2=max(ax1,a[y+1]);
if(ax1==ax2){
m[l++]=ax1;
// cout<<"ax1"<<ax1<<' ';
break;
}
//cout<<'y'<<y<<' ';
}
if(y==n-1){
m[l++]=ax2;
// cout<<ax2<<' ';
}
i=y;
}
}
ll sum=0;
for(int i=0;i<k;i++){
//cout<<'m'<<m[i]<<' ';
//cout<<endl;
//cout<<'t'<<t[i]<<endl;
sum+=m[i]-t[i];
}
cout<<sum;
return 0;
}
贪心:
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int a[N];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
ll sum=0;
for(int i=1;i<n;i++){
if(a[i-1]<a[i]){
sum+=a[i]-a[i-1];
}
}
cout<<sum;
return 0;
}
解析:
通过代码长度我们可以看出贪心和枚举算法的差别还是很挺大的,枚举用到了双指针i,j而且代码长,枚举的缺点是容易遗忘某种情况。
本题应多花点时间想一下贪心做法,贪心的特点是短视性和最优解这两个特点,本题对于两天的股票价格无非就是三种情况:上涨,下跌,不涨不跌,对于这三种情况显然当出现的上涨的情况时我们才应该买入股票,那么我们就看区间为1的购买股票方式,即贪心,最后验证最优解<=贪心即可确定贪心算法可。
那就把n天划分成若干个上升区间,累加和为贪心解这样的解的和一定是最大的。对于详情证明可看
解析
并且该题还可以用DP解决!!!