买卖股票的最佳时机121-力扣（数组+在线处理dp+c）

浅浅的花香味﹌ 2023-01-14 01:53 17阅读 0赞

题目描述  
买卖股票的最佳时机  
给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：\[7,1,5,3,6,4\]  
输出：5  
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。  
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。  
示例 2：

输入：prices = \[7,6,4,3,1\]  
输出：0  
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105  
0 <= prices\[i\] <= 104

题解  
分析：  
这道题目，最开始暴力求解会发现超时，其实对暴力解法简单处理一下就可以拿下这道题目了。

*  在我们暴力求解的时候，其实当我们从第 p r i c e s \[ i = 0 \] prices\[i=0\] prices\[i=0\]开始计算其与 p r i c e s \[ i > 0 \] prices\[i>0\] prices\[i>0\]的最大差max之后，再计算 p r i c e s \[ i \] ( i = 1 ) prices\[i\](i=1) prices\[i\](i=1)与 p r i c e s \[ j \] ( j > i ) prices\[j\](j>i) prices\[j\](j>i)之间的最大差的时候，如果 p r i c e s \[ i \] ( i = 1 ) prices\[i\](i=1) prices\[i\](i=1)的值大于或等于 p r i c e s \[ i = 0 \] prices\[i=0\] prices\[i=0\]的值，那么它与 p r i c e s \[ i > 1 \] prices\[i>1\] prices\[i>1\]的最大差肯定要小于或等于max，因此此时就不需要计算了。
 *  否则再循环计算 p r i c e s \[ i \] 与 p r i c e s \[ j \] ( j > i ) prices\[i\]与prices\[j\](j>i) prices\[i\]与prices\[j\](j>i)的最大差，然后与max进行比较并更新，并记录下prices\[i\]，这样后面的prices\[j\]只有比prices\[i\]小，获得的利益才有可能比prices\[i\]获得的利益大。

int maxProfit(int* prices, int pricesSize){ 
        int max = 0;
        int temp = prices[0];
        for(int i = 0; i < pricesSize - 1; i++)
        { 
            if(i >= 1 && prices[i] >= temp)
            { 
                continue;
            }
            else{ 
                temp = prices[i];
                for(int j = i+1; j < pricesSize; j++)
                { 
                    max = fmax(max, prices[j] - prices[i]);
                }
            }
        }
        return max;
    }

这样的话，时间复杂度就比 O ( N 2 ) O(N^2) O(N2)小，但是当prices是个递减数列时，最坏时间复杂度仍然是 O ( N 2 ) O(N^2) O(N2)。

进一步改进：

*  其实有了上面的理解之后，很轻松的可以理解在线处理这种方式：购买股票获取的利益其实就是从买入的那天开始，后面的每一天的涨跌情况的累计，购入后一旦利益累计小于0，那么就令累计利益归0。在这个过程中去判断累计利益的最大值。
 *  具体的，设置一个sum记录prices\[i\]与prices\[i+1\]之间的差值，然后逐步累加，一旦累计小于0就记为0，同时设置max作为最大利益，在累计时且每次比较获得max与sum的最大值。
 *  最后返回max
 *  其实可以看出来，在上面的设计过程中，获取的利益只于上一个状态获取的利益相关，这就是动态规划，其实我们也可以把这个动态规划方程表示出来： f ( i ) = f ( i − 1 ) + m a x \{ 0 , p r i c e s \[ i \] − p r i c e s \[ i − 1 \] \} f(i) = f(i-1)+max\\\{ 0, prices\[i\] - prices\[i-1\] \\\} f(i)=f(i−1)\+max\{ 0,prices\[i\]−prices\[i−1\]\}

int maxProfit(int* prices, int pricesSize){ 
        int sum = 0;
        int max = 0;
        for(int i = 0; i < pricesSize - 1; i++)
        { 
            sum += prices[i+1] - prices[i];
            max = fmax(sum, max);
            if(sum < 0)
            { 
                sum = 0;
            }
        }
        return max;
    }

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

关于在线处理，在求解[最大子序和][Link 1]的时候也用到过。在线处理其实就是动态规划，当前状态只于上一个状态有关。

[Link 1]: https://blog.csdn.net/qq_38048756/article/details/110676509