题解 | #买卖股票的最好时机#

太可笑了。。。我第一次跑出来 2ms 的成绩竟然使用暴力算法跑出来的。不过也可能是因为测试比较小的原因

超过了 90% 的 C++ 代码。。。

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int result = 0; 
        int tmp;
        for(int i =0; i < prices.size() - 1; ++i){
            for( int j = i+1; j < prices.size(); ++j ){
                tmp = prices[j] - prices[i];
                if(tmp > result) result = tmp;
            }
        }
        return result;
    }
};

时间复杂度是 O(n^2) 空间复杂度是 O(1)

另一种思路先预处理成差值，然后使用最大子数组的形式求解：

这种时间是 6ms

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int *profiles = new int[prices.size() - 1];
        // 计算差
        for(int i = 0; i < prices.size() - 1; ++i){
            profiles[i] = prices[i+1] - prices[i];
        }
        // 计算最大子数组
        int result = INT_MIN; 
        int tmp = 0;
        for(int i = 0; i < prices.size() - 1; ++i){
            tmp += profiles[i];
            if(tmp > result) result = tmp;
            if(tmp < 0 ) tmp = 0;
        }
        return result < 0 ? 0 : result;
    }
};

算法的时间复杂度是 O(2n) 空间复杂度是 O(n)

参照博客为 https://blog.nowcoder.net/n/854e8febecba4f1a835f04f9c1f921ac