题目描述

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
输入格式
第一行包含整数 N，表示数组长度。

第二行包含 N 个不大于 10000 的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

数据范围
1≤N≤105

样例

输入样例1：
6
7 1 5 3 6 4
输出样例1：
7
输入样例2：
5
1 2 3 4 5
输出样例2：
4
输入样例3：
5
7 6 4 3 1
输出样例3：
0

算法1

(贪心) $O(n)$

思想真的很重要 先不要急着做题 要优先找出题的规律 来构造一种这样的方法
比如本道题
如样例 1
7 1 5 3 6 4 结果为7
从中发现组合应该是 x = 1 y = 5 x= 3 y = 6 这两种组合和为7
样例2
1 2 3 4 5 组合应该为 x= 1, y = 5 组合结果为4
样例3
7 6 4 3 1 没有组合 所以结果为 0
这其中有什么规律呢
样例3当中单调递减没有组合
样例2中单调递增只有一组组合
样例1中有单调减为转变为单调增的转折点为x 单调增转变为单调减的转折为y 是不是和我们物理上的波峰和波谷有点类似
波谷和波峰之间的距离为波相距离的最大值 所以说我们这道题就有点类似波峰波谷问题 我们单调递减求波谷单调递增求波谷 这样我们选出其中所有的波峰波谷 是不是就可以求出最大值
这样我们来进行思想的代码化

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;

int ar[N];
int main()
{
    int n; cin>>n; int sum = 0;
    int x=1e9,y=0;
    for(int i=0;i<n;i++) cin>>ar[i];
    for(int i=0;i<n;i++)
    {
        if(ar[i]<y)
        {
            sum+=(y-x); y = 0; x =ar[i]; //当是一组波峰波谷后加上波峰波谷之间的距离
        }
        else if(ar[i]<=x) x = ar[i];  //求波谷
        else 
        {
            if(ar[i]>=y) y = ar[i];   //求波峰 
        }
    }
    if(y>x) sum+=(y-x); //判断最后一次是不是单调递增序列 如果是  再加上这一组“波峰波谷” 
    cout<<sum<<endl;
    return 0;
}