LeetCode/solutions/122. Best Time to Buy and Sell Stock II.md

# [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/)

update: LeetCode六道股票买卖题目总结见我的博客文章[动态规划之股票买卖系列](https://shusentang.github.io/2019/11/03/Buy-and-Sell-Stock/)

# 思路
## 比较好想的思路
如果分别知道了前0到前i天的最大利润dp[0...i]，那么前i+1天的最大利润就为：  
max(dp[j] + max(prices[i+1] - prices[k])), 其中k属于j~i+1   
以上思路时间复杂度为O(n^2), 空间复杂度为O(n)  
## 改进
运用贪心的思想：只要有利润(即prices[i] > prices[i-1])就可以买入卖出, 即不错过任何利润。  
此时时间复杂度O(n), 空间复杂度为O(1)

# C++
改进前：
``` C++
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int dp[prices.size()] = {0};
        int min_price;
        for(int i = 1; i < prices.size(); i++){
            min_price = prices[i];
            for(int j = i-1; j >= 0; j--){
                if(min_price > prices[j]) min_price = prices[j];
                if(dp[j] + prices[i] - min_price > dp[i]) dp[i] = dp[j] + prices[i] - min_price;    
            }
        }
        return dp[prices.size() - 1];
    }
};
```
改进后：
``` C++
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        for(int i = 1; i < prices.size(); i++)
            if(prices[i] > prices[i-1]) max_profit += (prices[i] - prices[i-1]);
        return max_profit;
    }
};
```