动态规划

买卖股票的最好时机

http://www.nowcoder.com/questionTerminal/64b4262d4e6d4f6181cd45446a5821ec

买卖股票的最好时机

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

  • 最优子结构

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

  • 重复子问题

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

动态规划解题步骤:

  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;
    }
}
全部评论

相关推荐

xdm怎么说&nbsp;要被拷打了&nbsp;担心是KPI
丹田:面就完了,就当日薪四位数的大佬免费给给你面试。
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务