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

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */

     /**
        思路:
        定义一个二维dp[][]   dp[i][0] 表示第i天不持股 拥有的钱
                            dp[i][1] 表示第i天持股   拥有的钱
        具体就是：在股价最低的时候买入 在股价最高的时候卖出
        当不持股时 如果前一天也不持股 那么什么也不做  如果前一天持股那么可以选择卖出
        dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);

        当持股时  如果前一天不持股 可以选择持股 如果前一天持股 则判断哪天持股更好

      */
    public int maxProfit (int[] prices) {
        // write code here
        //创建化状态方程
        int dp[][] = new int[prices.length][2];

        //初始化二维dp
        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];

    }
}