欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

力扣121. 买卖股票的最佳时机(动态规划)

程序员文章站 2022-07-16 09:58:25
...

力扣121. 买卖股票的最佳时机(动态规划)

力扣121. 买卖股票的最佳时机(动态规划)

动态规划:

有点像0-1背包问题:

买入:

  i当天买入 i当天不买入
i当天买入的最大收益 -i当天的股价 i-1买入的最大收益,维持现状
in[i] -prices[i] in[i-1]

卖出:

  i当天卖出 i当天不卖出
i当天卖出的最大收益 i-1天买入的最大收益+i当天的股价 i-1天卖出的最大收益,维持原状
out[i] out[i-1]+prices[i] out[i-1]

i-1天买入的最大收益,这里很多人不理解,以为仅仅是前一天的价格,其实i-1天买入的最大收益已经取最大值,即i-1天买入的最大收益代表第一天到第i-1天的最佳买入点,只是没有标记哪一天,直接相加即可。

复杂度分析:

  • 时间复杂度:O(N)
  • 空间复杂度:O(N)
//
//  main.cpp
//  121maxProfit
//
//  Created by MXQ on 2020/10/21.
//

#include <iostream>
#include<vector>
using namespace::std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0 || n==1)return 0;
        vector<int>in(n);
        vector<int>out(n);
        out[0]=0;
        in[0]=-prices[0];
        int maxoutvalue=0;
        for (int i=1; i<n; i++) {
            //转移方程
            in[i]=max(-prices[i],in[i-1]);
            out[i]=max(in[i-1]+prices[i],out[i-1]);
            if (out[i]>maxoutvalue) {
                maxoutvalue=out[i];
            }
        }
        return maxoutvalue;
    }
};
int main(int argc, const char * argv[]) {
    // insert code here...
    vector<int>prices={7,6,4,3,1};
    Solution s;
    auto result=s.maxProfit(prices);
    std::cout << result<<endl;
    std::cout << "Hello, World!\n";
    return 0;
}