题解 | #买卖股票的最好时机#

题目描述

假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。
示例1
输入：[1,4,2]
返回值：3

题目分析

在只有一次买入和卖出的机会的情况下，选择第 i 天买入，第 j 天卖出，则收益为 prices[j]-prices[i]，需要找到能够获得的收益最大值，如下图，计算出的最大值是3。

解题思路

方法1：暴力法
暴力遍历数组从 i 到 j （0<=i<j<n）的收益值（prices[j]-prices[i]），使用max记录出现的最大收益值；
想要遍历所有的i和j，需要两次遍历；

for(int i){
  for(int j){
  }
}

方法2：动态规划
使用动态规划数组dp，dp[i]表示前i天能够收益的最大值；
状态转移方程为： dp[i] = Math.max(dp[i-1], dp[i]-min);
这里面需要使用min，记录出现过的最小价格。

代码实现

方法1：暴力法

 public int maxProfit (int[] prices) {
        // write code here
        // 默认收益为0
        int max = 0;
        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                int profit = prices[j] - prices[i];
                // 当收益大于记录的值时，更新最大收益
                if(profit > max){
                    max = profit;
                }
            }
        }
        return max;
    }

时间复杂度：O(n^2)，n为数组的长度，两层循环的事件复杂度为n^2；
空间复杂度：O(1)，只需要常数的变量记录中间值和最大利益值；

方法2：动态规划

public int maxProfit (int[] prices) {
        // write code here
        if(prices == null || prices.length == 0) return 0;
        int len = prices.length;
        // 动态规划数组
        int dp[] = new int[len];
        int min = prices[0];
        for(int i=0;i<prices.length;i++){
            // 更新在i前的最小值
            if(prices[i] < min){
                min = prices[i];
            }
            if(i == 0){
                dp[i] = 0;
            }else{
                // 状态转移方程，dp[i]的值在dp[i-1]和（当前值-当前最小值）中的最大值
                dp[i] = Math.max(dp[i-1], prices[i]-min);
            }
        }
        // 返回最后的结果
        return dp[len-1];
    }

时间复杂度：O(n)，只需要遍历一遍数组；
空间复杂度：O(n)，需要n长度的辅助动态数组来帮助计算。