hiho 1604

题目链接

题目大意

小Hi最近在关注股票，为了计算股票可能的盈利，他获取了一只股票最近N天的价格A₁~A_N。

在小Hi的策略中，每天可以在下列三种操作中选取一种：

1.什么也不做；

2.按照当天的价格买进一个单位的股票；

3.按照当天的价格卖出部分或所有股票。

现在小Hi希望能够知道，如果在N天前手中持有的股票数为0，并且假设拥有无限的金钱，在这N天结束能够获得的最大利润是多少？

第一行包含一个整数N。  

第二行包含N个整数，A₁, A₂, ... A_N。  

对于30%的数据， 1 ≤ N ≤ 10³  

对于100%的数据，1 ≤ N ≤ 10⁶， 1 ≤ A_i ≤ 100

----------------------------------------------------------------------------------------------------------------------------

画下折线图就明白了，从后向前找，如果小于当前股票值 ans+=差值，这就是利润

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 1000100;
int A[N];

int main(){
    int n; cin>>n; int ans = 0;
    for(int i=0;i<n;i++) scanf("%d",A+i);
    for(int i=n-1;i>=0;){
        int j=i-1;
        for(;j>=0;j--){
            if(A[j]<A[i]) ans+=A[i]-A[j];
            else break;
        }
        i = j;
    }
    printf("%d
",ans);
    return 0;
}