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).
A: 算法2更好， 在最下面
------------------------3 rd pass -------------------
以前脑子不清醒。 这个明明就是2次分开的profit的情况。
也就是说，可以先找出最赚钱的那个情况，然后，再 找出左右两边的subarray中最赚钱的情况。然后二者相加即可。
嗯，还是算法2， 左右扫，更好些。
divide and conquer
设i从0到n-1，那么针对每一个i，看看在prices的子序列[0,...,i][i+1,...,n-1]上分别取得的最大利润（第一题）即可。
这样初步一算，时间复杂度是O(n2)。
经过和只买一次的情况对比，我们发现：
Idea:
分两种情况：
1： 第二个max和只有一个transaction时的数组（max1） 分离的。
最新的一遍，只考虑了这一种情况，大谬 ！！！！！！！！
2： max2与 max1有交际-----
public class Solution {
public static final int minValue = -100000;
public int maxProfit(int[] prices) {
// This is max profit for two transactions
if (prices != null && prices.length <= 1) {
return 0;
}
int[] change = new int[prices.length - 1];
for (int i = 0; i < prices.length - 1; i++) {
change[i] = prices[i + 1] - prices[i];
}
// return maxChange(change, 0, change.length - 1)[2];
// case 1:
// when the 2nd transaction independent of the 1st transaction
// i.e. they are disjoint
int[] max1 = maxChange(change, 0, change.length - 1);
// exclude the intervals from changes , to do second max
if(max1[2]<0){
return 0; // if the max buying profit in a single transaction is < 0
}
int[] modifiedChanges = new int[change.length];
for (int i = 0; i < change.length; i++) {
if (i >= max1[0] && i <= max1[1]) {
modifiedChanges[i] = minValue;
} else {
modifiedChanges[i] = change[i];
}
}
int[] max2 = maxChange(modifiedChanges, 0, change.length - 1);
//since when change = [1] only, the max 2 would return the above min_value;
int disJointMax = max1[2] + Math.max( max2[2],0); // we can reasonbalely assume that max2[2]>0
// Case 2:
// when two transactions are both intersect with the interval of one
// transaction
// we know that left and right terminal belongs to the two transactions.
// but they finally divided by the negative interval inside max1
// First we modify the changes.
for (int i = 0; i < change.length; i++) {
modifiedChanges[i] = -change[i];
}
int[] minInside = maxChange(modifiedChanges, max1[0], max1[1]);
if (minInside[0] - 1 < 0 || minInside[1] + 1 > change.length - 1) {
// actually this is the case 1
return disJointMax;
}
int[] maxLeft = maxChange(change, 0, minInside[0] - 1);
int[] maxRight = maxChange(change, minInside[1] + 1, change.length - 1);
int intersectMax = maxLeft[2] + maxRight[2];
if (disJointMax > intersectMax) {
return Math.max(disJointMax, 0);
} else {
return Math.max(intersectMax, 0);
}
}
// divide and conquere problem.
public int[] maxChange(int[] change, int start, int end) {
if (start == end) {
int[] tmp = { start, end, change[start] };
return tmp;
} else {
int middle = (int) ((start + end) / 2);
int[] leftMax = maxChange(change, start, middle);
int[] rightMax = maxChange(change, middle + 1, end);
int[] crossMax = maxCross(change, start, middle, end);
if (leftMax[2] >= rightMax[2] && leftMax[2] >= crossMax[2])
return leftMax;
if (rightMax[2] >= leftMax[2] && rightMax[2] >= crossMax[2])
return rightMax;
else
// (crossMax[2] >= leftMax[2] && crossMax[2] >= rightMax[2])
return crossMax;
}
}
private int[] maxCross(int[] change, int start, int middle, int end) {
// get max left part
int leftMax = 0;
int sum = 0;
int leftIndex = middle;
for (int i = middle; i >= start; i--) {
sum += change[i];
if (sum > leftMax) {
leftMax = sum;
leftIndex = i;
}
}
int rightMax = 0;
int rightIndex = middle + 1;
sum = 0;
for (int i = middle + 1; i <= end; i++) {
sum += change[i];
if (sum > rightMax) {
rightMax = sum;
rightIndex = i;
}
}
int[] tmp = { leftIndex, rightIndex, leftMax + rightMax };
return tmp;
}
}
Mistakes:
1： 没有考虑，可以有不买的选择，因此，当price =[2,1]时，输出了-1，而不是0.
Learned:
1:上面犯了一个错误。
原因在于，java的最小最大值如何运算，没搞清楚。看下面
System.out.println(Integer.MIN_VALUE); System.out.println(Integer.MIN_VALUE-1); 打印的结果为： -2147483648 2147483647
---------------------------第二遍， 有新解法----------------------------
思路来源于 这里
哎，其实，本题目的题意是这样的：
某一天买进， 再后面的一天卖出，这样就是利润。
因此，也只需要， 找到前面的一天最low的， 再找到后面的一天最high的 ， 就可以了。
问题1，之所以要用divide and conquere ，就是解决O(n)的问题，而且用了O(lg(n))的空间复杂度。
现在，我们放开， 就可以用O(n)的空间复杂度+ 时间复杂度 解决问题1.。。 DP思想。
那么，本问题III， 也可以用 类似的思想解决。
改进的方法就是动态规划了，那就是第一步扫描，先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。
第二步是逆向扫描，计算子序列[i,...,n-1]上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length <= 1 )
return 0;
int n = prices.length, minBefore = prices[0];
int maxProfitBefore[] = new int[n];
for(int i =1;i<n;i++){
maxProfitBefore[i] = Math.max(maxProfitBefore[i-1],prices[i] - minBefore);
minBefore = Math.min(minBefore, prices[i] );
}
// calculate last
int result = 0, maxAfter = prices[n-1];
for(int i=n-2;i>=0;i--){
result = Math.max(result, maxProfitBefore[i] + maxAfter - prices[i]);
maxAfter = Math.max(maxAfter, prices[i]);
}
return result;
}
}
No comments:
Post a Comment