LeetCode题目：Best Time to Buy and Sell Stock II
By
uniEagle |
2012 年 12 月 4 日 - 16:33 |
C++,
Develop,
算法
这个更简单了，题目要求可以多次买卖，但是同一时间只能有一股在手里。
这样就可以在每次上升子序列之前买入，在上升子序列结束的时候卖出。相当于能够获得所有的上升子序列的收益。
而且，对于一个上升子序列，比如：5，1，2，3，4，0 中的1，2，3，4序列来说，对于两种操作方案：
一，在1买入，4卖出；
二，在1买入，2卖出同时买入，3卖出同时买入，4卖出；
这两种操作下，收益是一样的。
所以算法就是：从头到尾扫描prices，如果i比i-1大，那么price[i] – price[i-1]就可以计入最后的收益中。这样扫描一次O(n)就可以获得最大收益了
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 you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock
before you buy again).
public class Solution {
public int maxProfit(int[] prices) {
if(prices==null|| prices.length<=1) return 0;
int profit = 0;
int i = 0;
while(i<prices.length){ //原来写的是for循环，与最下面 的i=j有重复！
int j = i+1;
for(;j<prices.length && prices[j]>prices[j-1];j++){ //循环条件都写错了...
}
profit += (prices[j-1]-prices[i]);
i = j; //不等于j+1
}
return profit;
}
}
3
和前两道题比起来的话，这道题最难了，因为限制了交易次数。
解决问题的途径我想出来的是：既然最多只能完成两笔交易，而且交易之间没有重叠，那么就divide and conquer。
设i从0到n-1，那么针对每一个i，看看在prices的子序列[0,...,i][i,...,n-1]上分别取得的最大利润（第一题）即可。
这样初步一算，时间复杂度是O(n2)。
改进：
改进的方法就是动态规划了，那就是第一步扫描，先计算出子序列[0,...,i]中的最大利润，用一个数组保存下来，那么时间是O(n)。
第二步是逆向扫描，计算子序列[i,...,n-1]上的最大利润，这一步同时就能结合上一步的结果计算最终的最大利润了，这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。
Best Time to Buy and Sell Stock III
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).
public class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<=1) return 0;
int[] max = new int[prices.length];
max[0] = 0;
int min=prices[0];
for(int i=1;i<prices.length;i++){
if(prices[i]<min){
min = prices[i];
max[i]=max[i-1];
}else{
int now = prices[i]-min;
max[i]= now>max[i-1]? max[i-1]; //变量名写错了啊啊啊
}
}
int allpro = max[prices.length-1]; //考虑[1,2] 0 1
int big = prices[prices.length-1]; int profit=0;
for(int i=prices.length-2;i>0;i--){
int temp = big-prices[i];
if(temp>profit) profit = temp;
if(prices[i]>big) big = prices[i];
if(profit+max[i-1]>allpro)
allpro = profit+max[i-1];
}
return allpro;
}
}