leetcode-buy-stock

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/best-time-to-buy-and-sell-stock//

　　你有n天股票的价格，现在可以选择在某天买入，某天卖出，求出能获得的最大利润

题目分析

　　数组s[i]代表可选天数是1~i天时，能获得的股票最大利润

　　s[i]=max{ max{ (v[i] - min{v[0]....v[i-1]}), 0 }, s[i-1] }

　　满足动态规划的条件

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxProfit(vector<int>& prices) {
    int s = prices.size();
    if(s < 2) return 0;
    int pre = 0;
    int minp = prices[0];
    for(int i = 1; i < s; i++) {
        int v1 = prices[i] - minp;
        if(v1 < 0) {
            v1 = 0;
        }
        int v2 = pre;
        if(prices[i] < minp) {
            minp = prices[i];
        }
        pre = (v1 > v2) ? v1 : v2;
    }
    return pre;
}

　　时间复杂度O(n)，额外空间复杂度O(1)