121. 买卖股票的最佳时机/面试题63. 股票的最大利润(简单)

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

思路1：

​ 找最大差值即可max(prices[j]-price[i]),j>i

前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)

profit=max(profit,prices[i]−min(cost,prices[i])

回看记录200726

了解了为什么dp[i][1]=Math.max(dp[i-1] [1],-prices[i]);，因为只能买卖一次股票，买股票一定是之前没有买股票

代码1：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE,profit =0;
        for(int price: prices){
            cost = Math.min(cost,price);
            profit = Math.max(profit,price-cost);
        }
        return profit;
    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//dp模板代码
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];//第几天是否持有股票的收益
        for(int i=0;i<n;i++){
            //base处理
            if(i-1==-1){
                dp[i][0]=0;
                dp[i][1]=-prices[i];
                continue;
            }
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);//只能买卖一次，必须从0开始买
        }
    return dp[n-1][0];
    }
}