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

//本题用动态规划求解，暴力搜索最简单
//设记忆化数组 为 dp【i】【j】i为天数 j长度为2 【0】【1】 dp代表了i天所持钱数
//0 代表今天不持股 1代表今天持股 

//当今天不持股时 ，有两种情况 ： 昨天不持股，或者昨天卖出
//状态转移方程为：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]);
import java.util.*;


public class Solution {

    public int maxProfit (int[] prices) {
		//暴力搜索
       /* int ans = 0;
        int max = 0;
        int temp =   0;

        for (int i = 0; i < prices.length; i++) {
            for (int j = i+1; j < prices.length ; j++) {
                temp = prices[j] - prices[i];
                if (temp > max){
                    max = temp;
                }
            }
        }
        ans = max;
        return  ans;*/

		//动态规划
        if (prices.length < 2){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        int ans = 0;

        dp[0][0] = 0 ;
        dp[0][1] = -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]);
            if (dp[i][0] > ans){
                ans = dp[i][0];
            }
        }
        return ans;
    }
}