每日一题（算法）—— 买卖股票(动态规划经典案例)

问题描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4]
输出：5

输入：prices = [7,6,4,3,1]
输出：0
1
2
3
4
5

解题思路：
由于这道题只需要求出最大收益，不需要找出第几天买入第几天卖出，可以考虑动态规划。
首先找到该问题的关键点：
1、找到最低价格
2、从最低价格开始找最高价

我们可以用两个变量来记录:
<1>最低成本price
<2>当前最大利益benefit
然后找到初始状态：初始利益为0，初始成本price为prices数组中第一个值。
转移状态：
1） 最大的利益benefit = Max( benefit，当天价格prices[i] - 最低成本price)
2） 最低成本price = Min（ 目前最低成本price，当天价格prices[i] ）。

int maxProfit(int* prices, int pricesSize){
    if (pricesSize < 2) return 0;
    int benifit = 0;
    int price = prices[0];
    for(int i=1;i<pricesSize;i++){
        if(benifit < prices[i] - price) benifit = prices[i] - price;
        if(price > prices[i]) price = prices[i]; 
    }
    return benifit;
}
1
2
3
4
5
6
7
8
9
10