LeetCode(DP)Best Time to Buy and Sell Stock

2018-06-15

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

思路：重点是“一次买卖”，想要找到一次买卖股票的最大利润，题目只要求返回最大利润，但是其实因为我们更关心一次买入一次卖出的最大利润，所以理论上返回最大利润以及买入卖出的时机应该更合理，为了解决这样的问题，我们需要保存每次产生利润的利润值以及买入卖出的时机，考虑到这两个数值的关联性，想到用map来装这些数据，随后返回最大利润即可，如有必要，也可返回获得最大利润时的买入，卖出时机。

java代码如下：

class Solution {
    public int maxProfit(int[] prices) {
    		int profit=0;
	        HashMap<Integer,int []> proMap=new HashMap<Integer,int []>();
	        int len=prices.length;
        	//防止数组越界的处理
	        if(prices.length==2){
                if(prices[0]<prices[1]){
                    return prices[1]-prices[0];
                }else{
                    return 0;
                }
            }
        	//找到第一个后者大于前者的点，然后计算利润
	        for(int i=0;i<len-1;i++){
	            if(prices[i]<prices[i+1]){
	                for(int j=i+1;j<len;j++){
	                	if(prices[j]>prices[i]) {
	                		profit=prices[j]-prices[i];
	     	                int [] arr=new int [2];
	     	                arr[0]=i;
	     	                arr[1]=j;
	     	                proMap.put(profit,arr);
	                	}
	                }
	            }
	        }
        	//如果map为空，说明市场不好不做买卖，利润为0
            if(proMap.isEmpty()){
                return 0;
            }
	        ArrayList<Integer> list=new ArrayList<Integer>();
	        for(Integer c : proMap.keySet()) {
	        	list.add(c);
	        }
	        list.sort(null);
	        return list.get(list.size()-1);
    }
}

　　上述算法其实还可优化，我们模拟人的选择过程，在上述方法中，如果我们选中了一天股票价格低于第二天的时候去买入，我们就以这一天的价格为准开始计算和后面的每一天价格做比较得到最大的利润，比如对于序列3,4,5,1,6,8。我们会先找到3这个点，然后分别计算4,5,6,8时候的利润，最后得到了最大利润是8-3=5,随后我们才会再找3后面的满足同样条件的点4（条件就是当前点的值小于下一个点的值）,这样计算肯定利润不会超过选中3时的利润，所以这一部分计算是重复无用的，此外，5也不是最大利润。只有当我们找到1这个点为买入点时，最后才能得到最大的利润为8-1=7。所以我们的算法应当这样改进：先买入序列的第一个点，然后判断它和后面的点的大小，如果后面的点比它大，就计算利润，并将这个利润值保存为当前的最大利润pmax，此时我们会计算p=4-3=1,pmax=1，然后是p=5-3=2，因为pmax<p,所以更新pmax=p=2。然后继续向后判断，如果能找到比当前买入的点（此时为第一个点）的价格还低的点，就放弃第一个点将这个价格更低的点作为买入点，比如我们在找到了1这个点时发现1<3，所以我们就将1当做买入点，然后从这个点出发再做和之前重复的判断，更新最大利润，找寻能产生更大利润的买入点，在这个序列里，后面不会再有比1还小的数了，所以我们的买入点不变，只是利润由6-1=5变为8-1=7，当运算到数组末尾的时候，这时候得到的最大利润就是一次买入卖出能得到的最大利润。代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit=0;
        int len=prices.length;
        if(len==0){
            return 0;
        }
        int bought=prices[0];
        for(int i=1;i<len;i++){
            if(bought<prices[i]){
                if(maxprofit<prices[i]-bought){
                    maxprofit=prices[i]-bought;
                }
            }else{
                bought=prices[i];
            }
        }
        return maxprofit;
    }
}