# 121. Best Time to Buy and Sell Stock
###### tags: `Leetcode` `Easy` `Dynamic Programming`
Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
## 思路
### 思路一 暴力解法（超时）
双层回圈 算出每两个数的差 找出最大值
### 思路二 DP（超时）
一开始被dp困住了...认准它要用dp解
dp表格 **如果题目要求最大值，并不一定是每个格子都存最大值~**
于是用了一个nums.length*numslength的array，对角线下面都是0, dp[i][j]代表在第i天及以后买入，在第j天及以前卖掉的最大利润
也就是``` dp[i][j] = max(dp[i][j-1],dp[i-1][j], nums[j]-nums[i])```
### 思路三

我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

**另一种理解**
可以看做一种动态规划，只不过对空间复杂度进行了优化。考虑每次如何获取最大收益？第i天的最大收益只需要知道前i天的最低点就可以算出来了。而第i天以前（包括第i天）的最低点和i-1天的最低点有关，至此我们的动态方程就出来了。

dp[i] = min(d[i-1],prices[i])
其中dp[0]=prices[0],然后动态计算之后的就可以了。 得到了前i天的最低点以后，只需要维护一个max用来保存最大收益就可以了。 这个时候是空间复杂度O（n）的动态规划
接着考虑优化空间，仔细观察动态规划的辅助数组，其每一次只用到了dp[-1]这一个空间，因此可以把数组改成单个变量dp来存储截止到第i天的价格最低点。
## Code
### 思路一

public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

### 思路二

class Solution {
    public int maxProfit(int[] prices) {
        int [] dp = new int[prices.length];
        for(int i = 0;i < prices.length-1;i++){
            for(int j = i+1;j < prices.length;j++){
                dp[j] = Math.max(Math.max(prices[j]-prices[i], dp[j]),dp[j-1]);
            }
        }
        return dp[prices.length-1];
    }
}

### 思路三

public class Solution {
    public int maxProfit(int prices[]) {
        int minPoint = prices[0];
        int maxProfit = 0;
        for(int price:prices){
            if(minPoint > price){
                minPoint = price;
            }
            if(price-minPoint>maxProfit){
                maxProfit = price-minPoint;
            }
        }
        return maxProfit;
    }
}

## Result
### 思路三
Runtime: 3 ms, faster than **24.34%** of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 105.6 MB, less than **9.00%** of Java online submissions for Best Time to Buy and Sell Stock.