My code:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0 || prices.length == 1)
return 0;
int[] left = new int[prices.length];
int[] right = new int[prices.length];
getMaxProfit(left, right, prices);
int[] sum = new int[prices.length];
int max = 0;
for (int i = 0; i < prices.length; i++) {
sum[i] = left[i] + right[i];
if (max < sum[i])
max = sum[i];
}
return max;
}
private void getMaxProfit(int[] left, int[] right, int[] prices) {
int min = prices[0]; //represent the min prices
int max = 0; //represent the max profit
for (int i = 1; i < prices.length; i++) {
int temp = prices[i] - min;
if (temp < 0) {
left[i] = max;
min = prices[i];
}
else if (temp <= max)
left[i] = max;
else {
left[i] = temp;
max = temp;
}
}
int rightMax = prices[prices.length - 1];
int profitMax = 0;
for (int i = prices.length - 2; i >= 0; i--) {
int temp = rightMax - prices[i];
if (temp < 0) {
right[i] = profitMax;
rightMax = prices[i];
}
else if (temp < profitMax)
right[i] = profitMax;
else {
right[i] = temp;
profitMax = temp;
}
}
}
}
My test result:
这次作业没能有自己的思路，然后看了一篇博客，写的很好，思路很明确清晰，于是我按照这个思路自己写了出来。
顺便把这个系列的题目总结下吧。
第一题，就是给你一串数，然后买进卖出，最多只做一次交易，求最大利润。
那么，其实就是，DP，从 i = 1开始，不断地向前递进，每一次，
计算下prices[i] - min 的值，
如果大于max，那就设这个值为max，
如果小于max但>=0，则保持max， min不变。
如果小于0，则更新min为当前值。
所以说，max代表的是当前范围内的最大利润，而min表示当前范围内的最大利润中，买进的价格。不一定是当前范围内的最小值。
然后遍历一遍即可以得出结果。
第二题，同样是一串数，买进卖出。但是，允许无限次交易，求最大利润。
因为允许无限次交易。可以设置一个数组diff[]，用来记录前后两个数的差值，
如果大于0，则全部累加到变量max上。
如果小于0，就不加。
遍历结束后，该max即为最大利润。
为什么？
比如，2, 3, 5, 7
如果是递增数列，那么
7 - 2 = (3- 2) + (5- 3) + (7 - 5)
如果出现递减的，比如，2, 1, 5, 3, 7
这里就有一个注意点，如果是无限次交易，那我就是买进1，卖出5，然后买进3卖出7，这样赚的最多，所以可以累加。可以把每一次出现的递减点，当做是新的一次交易的买进值。
但是，如果限制只允许一次交易，那么就该是，买进1，卖出7。即需要采用第一题的思路了。
第三题，同样是一串数，买进卖出，但是，只允许最多两次交易，求最大利润。
所以，可以把数组一切为2，[0, i] 为第一次交易， [i, prices.length - 1] 为第二次交易。
特定到i点时，可在i点把货物卖出，作为[0, i]区域的终结，然后再i点把货物买入， 作为[i, prices.length - 1]区域的开始，
于是可以设置两个数组，left[], right[]
left[i] 表示 [0, i] 这么一段区域内，交易一次最大的利润。可以用第一题的算法来解决。
right[i] 表示 [i, prices.length - 1] 这么一段区域内，交易一次最大的利润，可以反过来用第一题的思路来解决。
left[i] + right[i] 即等于在第i天时为分界点进行两次交易的最大利润值。
然后遍历获得这些分界点利润最大值中的最大值，即为我们需要的最大利润。
我觉得文章里有句话说的挺对的，
看来以后碰到与2相关的问题，一定要想想能不能用二分法来做！
http://blog.csdn.net/fightforyourdream/article/details/14503469
第四题，等等更新。
放弃吧。。。。感觉好他妈复杂。具体做法有时间还是看上面那个网页对应的文章。
最后还是测试过了，但主要还是拷贝了代码，这道题目真的很难啊。。。逻辑复杂，代码简单。需要考虑的一个情况是，
当 k >= prices.length， 的时候，就直接用
Best Time to Buy and Sell Stock II 的无限次交易方法来做，测试就过了。http://www.cnblogs.com/grandyang/p/4295761.html
**
总结：DP 以后碰到与2相关的问题，一定要想想能不能用二分法来做！
老爸好像吃坏肚子了，然后拉肚子之后还发烧，感觉爸妈的身体真的没以前好了，如果我不在家，他们。。。不能去想了。要想走出去，必须得有牺牲。
我们不是贵族阶级。
**
Anyway, Good luck, Richardo!
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0 || prices.length == 1)
return 0;
int[] profits = new int[prices.length];
int[] left = new int[prices.length];
int[] right = new int[prices.length];
process(prices, left, right);
for (int i = 0; i < profits.length; i++)
profits[i] = left[i] + right[i];
Arrays.sort(profits);
return profits[profits.length - 1];
}
private void process(int[] prices, int[] left, int[] right) {
left[0] = 0;
right[right.length - 1] = 0;
int min = prices[0];
for (int i = 1; i < left.length; i++) {
left[i] = Math.max(left[i - 1], prices[i] - min);
min = Math.min(min, prices[i]);
}
int max = prices[prices.length - 1];
for (int i = right.length - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], max - prices[i]);
max = Math.max(max, prices[i]);
}
}
}
---- 09/23/2015 23:17
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1)
return 0;
int max = 0;
int[] profits = new int[prices.length];
int buy = prices[0];
/** 1: [0, i]; 2: [i + 1, prices.length - 1]
* scan for transaction 1, [0, i], i++
*/
for (int i = 1; i < prices.length; i++) {
if (prices[i] >= buy) {
max = Math.max(max, prices[i] - buy);
}
else {
buy = prices[i];
}
profits[i] = max;
}
/** scan for tracnsaction 2, [i + 1, prices.length - 1], i-- */
int sell = prices[prices.length - 1];
max = 0;
for (int i = prices.length - 2; i >= 0; i--) {
if (prices[i + 1] <= sell) {
max = Math.max(max, sell - prices[i + 1]);
}
else {
sell = prices[i + 1];
}
profits[i] += max;
}
Arrays.sort(profits);
return profits[profits.length - 1];
}
}
一开始做的超时了。因为有许多重复操作。
然后改了下。做了出来，没看答案。虽然原来的做法还有些印象。
Anyway, Good luck, Richardo!
差不多的思路。
今天找人投了 amazon, ea, 还有校招的 two sigma
全职之战开始了。
好运。
Anyway, Good luck, Richardo! -- 08/19/2016
