贪心算法

算法思路：贪心规律

1、超级重要的一个性质：在我们这个数组里面，也就是 1 到 n 天里面，我们任意跨天数（也就是买卖的天数不是相邻的，这天买然后过几天卖）的交易，都是可以被拆分的

2、而且我们可以把上述的跨天数的交易全部拆分成跨度为一天的交易，也就是今天买然后明天就卖

3、也就是说，无论你的决策如何买卖，都能转化成很多个跨度为一天的交易，然后拼起来，就等价于这个决策

4、那么问题也就迎刃而解了，既然无论如何买卖我们都可以进行拆分，那么我们就只需要直接执行拆分后的情况就好了

5、所以说最终我们就可以分别独立的去看每相邻两天之间的差距了

6、那我们只需要从头遍历一下整个数组，如果我们后一天的股票价格大于我们前一天的股票价格，那么我们就交易。

7、这样子我们的答案就出来了

下面是简洁的C++代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;

typedef long long LL;

int n;

int a[N];

int main()
{
    scanf("%d",&n);

    LL ans=0;

    a[0]=0x3f3f3f3f;//防止第一天交易

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]>a[i-1])//如果我们当前的股票价格大于前一天的，那么我们就交易
        ans+=a[i]-a[i-1];
    }

    printf("%d",ans);

    return 0;
}