零花钱(money.cpp) 

【问题描述】 

商店里有一件玩具，今天你偶然得知：这件玩具在后⾯的n天里每天的定价（价格可能每天都会改 变），你买了这件玩具后可以以当天的价格卖给商店，所以你可以通过买卖这件玩具来赚取零花钱。如果只允许买卖一次，你怎样才能赚到最多的钱？数据保证肯定能赚到钱。

【输入描述】

第一行：⼀个正整数n，表示有n天。

第二行：a1,a2,...,an，表示这件玩具在将来n天里每天的价格，中间一个空格隔开。

【输出描述】

一个整数，最多能够赚多少零花钱。

【样例输入】

4  1 2 3 5

【样例输出】

4

【数据规模和约定】

50%的数据：0<n<=1000, 1<=a1<=a2<=...<=an<=1000；

100%的数据：0<n<=100000, 1<=a1,a2,…,an<=1000。

【题目分析】

• 首先明白一个点，不是每天必须都要买的，某一天可以不用买。

• 这一天过去了就不能再卖了。

• 如果求出数组中的最大值max的下标indexMax比数组中的最小值min的下标indexMin大，那么结论就是max-min(样例中的情况)

• 如果数组中最大值max的下标indexMax比最小值min的下标indexMin小。比如（5，6，2，1，3）这个时候就需要详细考虑了。

  （5，6，2，1，3）最大值是6，最小值是1，但是因为一天过去了就不能用昨天的价格卖出，所以多能赚的是第4天买，第5天卖，赚2元。

  那么我们就要讨论一下数据的规律，可以简单看出，数据可以分成几类，由小到大，由大到小。由大到小的没法考虑，所以我们只考虑由小到大。因为不是按照顺序由小达到，是“一段一段”的由小到大。所以可以考虑把每一段的 由小到大 的结果算出来。然后求最大或者最小。

【参考答案】

#include<bits/stdc++.h>  using namespace std;  int main(){  	int a[100000];  	int n,pmax=0,pmin=10001,indmax,indmin;  	cin>>n;  	for(int i=0;i<n;i++){  		cin>>a[i];  	}  	for(int i=0;i<n;i++){  		if(pmax<a[i]){  			pmax=a[i];  			indmax=i;  		}  		if(pmin>a[i]){  			pmin=a[i];  			indmin=i;  		}  	}  	if(indmax>=indmin){  		cout<<pmax-pmin;  	}else{  		int tmpmin=10001;  		int tmpmax=0;  		for(int i=0;i<indmax;i++){  //从开始位置到最大值所在位置  			if(tmpmin>a[i]){  				tmpmin=a[i];  //找最小值  			}  		}  		  		for(int i=indmin;i<n;i++){  //从最小值所在位置到结束，  			if(tmpmax<a[i]){  				tmpmax=a[i];   //找最大值  			}  		}  		int cj=pmax-tmpmin;  //用原来的最大值减去从0到最大值下标之间的最小值  		int cj2=tmpmax-pmin; //用从最小值下标到结束之间的最大值减去原来的最小值。  		if(cj>cj2){  			cout<<cj;  		}else{  			cout<<cj2;  		}  	}  	return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});