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

import java.util.*;


public class Solution {
    /**
     *
     * @param prices int整型一维数组
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int len = prices.length;
        if (len < 2) return 0;		// 天数小于2时，直接返回0
        int[] dp = new int[len];    // 记dp[i]表示第i+1天卖出可获得的最大收益
        dp[0] = 0;	// 第1天卖出时可获得的最大收益为0（第1天还没有买入）
        dp[1] = prices[1] - prices[0];	// 第2天卖出时可获得的收益只有一种情况，即第1天买入，第二天卖出
        int max = dp[1];	// max来记录最大收益
	  	// 遍历数组，更新dp[i]
        for (int i = 2; i < len; i++) {
            int d = prices[i] - prices[i - 1];	// 第i+1天和第i天的价格差为d
		  	// 这里dp[i]的值有两种情况。假设dp[i-1]在第1到第i天中间的第m天买入股票，第i天卖出股票。
		  	// 1: 不改变买入股票的天数，依然在第m天买入股票，但是在第i+1天卖出股票。
		  	//    此时的收益为dp[i-1]+d，这样获得的收益可能比第i天卖出股票多，也可能少（因为d可能小于0）。
		  	// 2: 改变买入股票的天数（此时不选择第1~第i天中间除了第m天以外的时机买入，
		  	//    因为其他时机买入都比第m天买入获得的收益少，
		  	//    因为d[i-1]表示的是第i-1天卖出可获得的“最大收益”），
		  	//    由于不选择第i~第i天中间的时机买入，那么只能选择第i天买入股票，第i-1天卖出股票
		  	//	  此时的收益为d
		  	// 取dp[i-1]+d 和 d 这两者中的较大值作为dp[i]的值，即第i+1天卖出股票可获得的最大收益 
            dp[i] = Math.max(d + dp[i - 1], d);	
		  	// 如果第i+1天卖出股票可获得的最大收益比之前的1~i天的某一天卖出股票可获得的最大收益大，
		  	// 则更改max的值
            max = Math.max(max, dp[i]);
        }
	  	// 判断最大收益max是否大于0，如果小于0则返回0，否则返回max
        return max > 0 ? max : 0;
    }
}