动态规划

买卖股票的最好时机

这是一个典型的动态规划问题。

• 最优子结构

  在自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖于它们解的原问题自然也是全局最优解。

• 重复子问题

  递归地寻找子问题的最优解时，子问题会重叠地出现在子问题里，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。

动态规划解题步骤：

1. 定义子问题
2. 写出子问题的递推关系
3. 确定DP数组的计算顺序

本题中的具体表现为：

dp[i]   i天卖出的最大收益
buy 买进日期
sell 卖出日期
dp[i] = 今天卖出日期-最小买进日期;
dp[0] = 0;

题解：

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int res = 0;
        int len = prices.length;
        int dp =  prices[0];
        int buy = prices[0];
        int sell = prices[0];
        for(int i = 1; i < len; i++){
            sell = prices[i];
            if(sell < buy) buy = sell;
            dp = sell - buy;
            res = Math.max(dp, res);
        }

        return res;
    }
}