题解 | 买卖股票的最好时机(一)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int[][] dp=new int[prices.length][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<prices.length;i++){
            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]);
        }
        return dp[prices.length-1][0];
    }
}

动态规划算法

1、用dp[][]数组来表示当天卖掉股票或者没卖掉股票的最大利益，dp[][0]表示卖掉了，dp[][1]表示继续持有

2、第一天的如果卖掉或者说没买的时候利益为0，第一天买入的话利益为-prices[0];

3、后续如果当天卖掉的话，那最大利益应该是前一天卖掉的利益与前一天没卖掉的利益加上今天的股价来做最大比较。

4、如果当天还是不卖掉或者说当天才买入，那么最大利益是前一天持有的利益与当天买入的股价做比较。

该题还可以用贪心算法来求解

就是求买入股价与卖出股价的最大差值。也就是说要在最低价的时候购入，最高价的时候卖出。

public int maxProfit (int[] prices) {

        // write code here

        int res=0;

        int Min=prices[0];

        if(prices.length==1){

            return res;

        }

        for(int i=1;i<prices.length;i++){

            Min=Math.min(Min,prices[i]);

            res=Math.max(res,prices[i]-Min);

        }

        return res;

    }