给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
image.png
思路：
先买 后卖。
如果只有一天的数据，买了再卖 0元。
如果有两天的数据，比较前者时不是 小于 后者（后者中最大的），小于则，后者-前者元。
类推，但是我们要记录一个东西，后者中钱最大的值和后者中最大的利润。
int maxProfit(int* prices, int pricesSize) {
if(pricesSize<=1)
return 0;
typedef struct {
int max;
int money;
}gu;
gu a[pricesSize];
a[pricesSize-1].money = 0;
a[pricesSize-1].max = prices[pricesSize-1];
int max1 = 0;
for(int i = pricesSize-2;i>=0;i--){
if(prices[i]>=a[i+1].max){
a[i].money = 0;
a[i].max = prices[i];
}else{
a[i].max = a[i+1].max;
a[i].money = a[i+1].max-prices[i];
}
if(max1 < a[i].money)
max1 = a[i].money;
}
return max1;
}
[leetcode 原题]（https://leetcode-cn.com/explore/interview/card/tencent/226/dynamic-programming/923/）
