苏苏酱陪你学动态规划（一）——股票买卖

叁歲伎倆 2022-04-18 04:07 157阅读 0赞

## 1、问题描述 ##

给你一串数字，表示每天的股票价格，你在某一天买进，并在未来的某一天卖出，请求出最大的利润值。

例：

1，2，6，4，3

那么应该在第一天买进，第三天卖出，最多赚5

## 2、解题思路 ##

截至某一天，最大的利润值其实之和它前一天的最大利润值有关，那么采用记忆化自低向上的求解方法即可求得最优解。时间复杂度为O(n)。

## 3、JAVA程序实现 ##

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class best_time_to_buy_and_sell_stock{
    
    	public static void main(String[] args) throws IOException{
    		// TODO Auto-generated method stub
    		/*
    		 * price[i]:the price of each day
    		 * L[i]:lowest price up to i-th day
    		 * P[i]:max profit up to i-th day
    		 * P[i] = max(P[i-1],price[i]-L[i-1])
    		 */
    		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	    String line = in.readLine();
    	    String[] s = line.split(" ");
    	    int[] price = new int[s.length];
    	    for(int i = 0 ; i<s.length;i++) {
    	    	price[i] = Integer.parseInt(s[i]);
    	    }
    	    
    	    int[] L = new int[price.length];
    	    int[] P = new int[price.length];
    	    L[0] = price[0];
    	    P[0] = 0;
    	    
    	    for (int i = 1; i<price.length;i++) {
    	    	L[i] = Math.min(L[i-1],price[i]);
    	    	P[i] = Math.max(P[0], price[i]-L[i-1]);
    	    	
    	    }
    	    System.out.println(P[P.length-1]);
    	}
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关算法[动态规划]---买卖股票最佳时机

1、题目：给你一个整数数组 prices，其中 prices\[i\] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任

超、凢脫俗/ 2024年03月04日 08:07/ 0 赞/ 189 阅读

相关 leetcode动态规划（买卖股票问题）

1. 买卖股票的最佳时机给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，

怼烎@/ 2022年09月05日 15:51/ 0 赞/ 233 阅读

相关 [Leetcode 动态规划]买卖股票

转自http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html

小灰灰/ 2022年06月08日 08:59/ 0 赞/ 213 阅读

相关动态规划---最好的一天买卖股票

1、题目 Say you have an array for which the ith element is the price of a given stock on d

小鱼儿/ 2022年05月23日 07:47/ 0 赞/ 173 阅读

相关动态规划之买卖股票的最佳时机——Leecode

1.题目：买卖股票的最佳时机 [https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/desc

浅浅的花香味﹌/ 2022年05月11日 10:20/ 0 赞/ 203 阅读

相关苏苏酱陪你学动态规划（一）——股票买卖

1、问题描述给你一串数字，表示每天的股票价格，你在某一天买进，并在未来的某一天卖出，请求出最大的利润值。例： 1，2，6，4，3 那么应该在第一天买进，第三天卖

叁歲伎倆/ 2022年04月18日 04:07/ 0 赞/ 158 阅读

相关苏苏酱陪你学动态规划，拿名企offer

转眼间我已经是一名研三的老学长，时间飞快，感谢互联网知识社区在我成长中给我的帮助。没有互联网社区的知识共享，很多知识我也难以快速了解；没有互联网社区的知识共享，我也不会发现原来

亦凉/ 2022年04月18日 03:19/ 0 赞/ 180 阅读

相关苏苏酱陪你学动态规划（二）——合唱团

1、问题重述有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生

桃扇骨/ 2022年04月16日 04:29/ 0 赞/ 209 阅读

相关苏苏酱陪你学动态规划（三）——背包问题

1、0-1背包问题背包问题的典型描述如下：一、假如你是奥特曼，有N点的攻击力，现在有一些小怪兽，每一个小怪兽被打倒都需要消耗你一定数量的攻击力，同时你将获得该怪兽对

清疚/ 2022年03月12日 11:30/ 0 赞/ 229 阅读

相关 121. 买卖股票的最佳时机（动态规划）

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意你

古城微笑少年丶/ 2021年06月22日 15:37/ 0 赞/ 433 阅读