Finley.Hamilton

# 题目

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;
}
}
``````

``````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 这篇文章做了有益的补充，但是题目并不允许一天之内进行的买卖。

### Finley.Hamilton

Leetcode 121. 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......

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

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

SnailTyan
2018/10/30
0
0

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

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服务

5
0

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