文档章节

Best Time To Sell Stock 3

Finley.Hamilton
 Finley.Hamilton
发布于 2014/12/04 11:45
字数 551
阅读 39
收藏 0

题目

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

#思路

  • 一开始是想定义一个点i,d[i]表示在i点之前卖掉第一次股票所得到的最大利润,这个狂野的想法很明显是要TLE的,最关键的问题是,进行了过多的重复计算,[i...n]和[i+1...n]的最大利润在prices[i+1] < prices[i]的时候是一样的

  • 参考了别人的思路,分别算[0...i]的最大利润和[i...n]的最大利润,很明显[0...i]的最大利润的算法跟之前Stock1的解法是一样的,但是后面[i...n]的解法就更为暴力一点,从后往前扫,遇到最高的就记下来,最大利润就是当前max(highest - prices[i], maxproofit)。

#代码

public class Solution {
    public int maxProfit(int[] prices) {
        
        if (prices.length == 0) {
            return 0;
        }
        
        // calculating [0...i] max profit
        int[] leftMaxProfit = new int[prices.length];

        // calculating [i...n] max profit
        int[] rightMaxProfit = new int[prices.length];


        leftMaxProfit[0] = 0;
        for (int i = 1; i < leftMaxProfit.length; i++) {
            int changes = prices[i] - prices[i - 1];
            leftMaxProfit[i] = leftMaxProfit[i - 1] + changes < 0 ? 0 : leftMaxProfit[i - 1] + changes;
        }

        rightMaxProfit[0] = 0;
        int highest = prices[prices.length - 1];
        int maxprofit = Integer.MIN_VALUE;
        int ret = 0;
        for (int i = rightMaxProfit.length - 1; i >= 1; i--) {
            int profit = highest - prices[i];
            if (profit > maxprofit) maxprofit = profit;
            int finalprofit = maxprofit + leftMaxProfit[i];
            if (finalprofit > ret) ret = finalprofit;
            if (prices[i] > highest) highest = prices[i];
        }
        return ret;
    }
}

起手后头那一段可以用更动态规划的方法改写,参考了http://blog.csdn.net/fightforyourdream/article/details/14503469

right[right.length-1] = 0;  
int max = prices[right.length-1];       // 最高卖出价  
// 右边递推公式  
for(int i=right.length-2; i>=0; i--){  
    right[i] = Math.max(right[i+1], max-prices[i]); // i的最大利润为(i+1的利润)和(最高卖出价和当前买入价之差)的较大那个  
    max = Math.max(max, prices[i]);     // 更新最高卖出价  
}  

http://blog.csdn.net/fightforyourdream/article/details/14503469 这篇文章做了有益的补充,但是题目并不允许一天之内进行的买卖。

仅仅从思路上看,“进行K次交易所得到最大的利润”也是个不错的思考方向

© 著作权归作者所有

共有 人打赏支持
Finley.Hamilton

Finley.Hamilton

粉丝 5
博文 45
码字总数 15431
作品 0
广州
私信 提问
Leetcode 121. Best Time to Buy and Sell Stock

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Version 3 Reference https://leetcode.com/problems/best-time-to-buy-and-sell-stock......

SnailTyan
2018/10/19
0
0
Leetcode-Easy 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock 描述: 思路: [1,2,3,4] ==> returns 3 (buy at 1 and sell at 4) [4,3,2,1] ==> returns 0 (don't buy) [4,10,25,2,10] ==> returns 21 (buy at 4 a......

致Great
2018/04/01
0
0
LeetCode 309. Best Time to Buy and Sell Stock with Cooldown (在具有冻结时间条件下买入和卖出股票的最佳时间)

原题 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transaction......

dby_freedom
2018/12/06
0
0
122. Best Time to Buy and Sell Stock II。

Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as ......

Leafage_M
2018/01/26
0
0
Leetcode 122. Best Time to Buy and Sell Stock II

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/83546622 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
2018/10/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java框架学习日志-13(Mybatis基本概念和简单的例子)

在mybatis初次学习Mybatis的时候,遇到了很多问题,虽然阿里云的视频有教学,但是视频教学所使用的软件和我自己使用的软件不用,我自己用的数据库是oracle数据库,开发环境是idea。而且视频中...

白话
今天
4
0
Java基础:String、StringBuffer和StringBuilder的区别

1 String String:字符串常量,字符串长度不可变。Java中String是immutable(不可变)的。 String类的包含如下定义: /** The value is used for character storage. */private final cha...

watermelon11
今天
2
0
mogodb服务

部署MongoDB 官网: https://www.mongodb.com/download-center/community 创建mongo数据目录 mkdir /data/mongodb 二进制部署 wget -c https://fastdl.mongodb.org/linux/mongodb-linux-x8......

以谁为师
昨天
5
0
大神教你Debian GNU/Linux 9.7 “Stretch” Live和安装镜像开放下载

Debian项目团队于昨天发布了Debian GNU/Linux 9 "Stretch" 的第7个维护版本更新,重点修复了APT软件管理器中存在的安全漏洞。在敦促每位用户尽快升级系统的同时,Debian团队还发布了Debian ...

linux-tao
昨天
4
0
PHP 相关配置

1. php-fpm的pool 编辑php-fpm配置文件php-fpm.con vim /usr/local/php/etc/php-fpm.conf //在[global]部分增加以下内容 include = etc/php-fpm.d/*.conf # 相当与Nginx的虚拟主机文件 “vho......

Yue_Chen
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部