学步园

Best time to Buy and Sell Stock

我的思路：

1、给定一个数组，表示每日股价，最多只能买入和卖出一次，给出最大收益。

2、这题在算法导论的第一章就有，用的递归，这是求最大数组，每个最大数组都只有三种出现的可能。第一种是数组左边，第二种，数组右边，第三种，跨越了数组。在core函数进行递归调用，只需要对跨越中间的最大子数组进行合并。

代码如下：

#define MIN 0

struct data {
	int left;
	int right;
	int sum;
};

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (!prices.size() || prices.size() == 1)
    		return 0;
    	vector<int> changes;
    	int			tmp;
    	for (int i = 0; i < prices.size() - 1; i++) {
    		tmp = prices[i + 1] - prices[i];
    		changes.push_back(tmp);
    	}
    	data ans = findMaximumSubarray(changes, 0, changes.size() - 1);
    	if (ans.sum < 0)
    	    return 0;
    	else 
    	    return ans.sum;
    }
    
private:
    data findMaximumSubarray(vector<int> &changes, int low, int high) {
    	if (high == low) {
    		data d;
    		d.left = low;
    		d.right = high;
    		d.sum = changes[low];
    		return d;
    	}
    	else {
    		int mid		= (low + high) / 2;
    		data leftd	= findMaximumSubarray(changes, low, mid);
    		data rightd	= findMaximumSubarray(changes, mid + 1, high);
    		data midd	= findMaxCrossingSubarray(changes, low, mid, high);
    		if (leftd.sum >= rightd.sum && leftd.sum >= midd.sum)
    			return leftd;
    		else if (rightd.sum >= leftd.sum && rightd.sum >= midd.sum)
    			return rightd;
    		else 
    			return midd;
    	}
    }
    data findMaxCrossingSubarray(vector<int> &changes, int low, int mid, int high) {
    	data d;
    	int leftsum = MIN;
    	int sum = 0;
    	for (int i = mid; i >= low; i--) {
    		sum += changes[i];
    		if (sum > leftsum) {
    			leftsum = sum;
    			d.left = i;
    		} 
    	}
    	int rightsum = MIN;
    	sum = 0;
    	for (int i = mid + 1; i <= high; i++) {
    		sum += changes[i];
    		if (sum > rightsum) {
    			rightsum = sum;
    			d.right = i;
    		}
    	}
    	d.sum = leftsum + rightsum;
    	return d;
    }
};

别人思路：

1、如此简单，让人心碎。遍历数组，获取数组中最小的值，如果该值不是最小，判断和之前的相比收益有没有提高，提高就改变收益。

    int maxProfit(vector<int> &prices) {
        if (!prices.size())
            return 0;
        int min = prices[0], profit = 0;
        
        for (int i = 1; i < prices.size(); i++)
            if (min > prices[i])
                min = prices[i];
            else 
                if (profit < prices[i] - min)
                    profit = prices[i] - min;
        
        return profit;
    }

反思：

1、其实自己就差一点就想到这个思路了，但是想起算法导论就现成了，就直接拿来用了。。。懒人穷三代。

Best Time to Buy and Sell Stock II

我的思路：

1、这题就是能买卖多次，但是下次买之前要先卖。代码类似，太简单就不贴别人的思路了，应该差不多。

    int maxProfit(vector<int> &prices) {
        if (prices.size() <= 1)
            return 0;
        int profit = 0, min = prices[0];
        
        for (int i = 1; i < prices.size(); i++) 
            if (prices[i] > prices[i - 1])
                profit += prices[i] - prices[i - 1];
        
        return profit;
    }

Best Time to Buy and Sell Stock III

我的思路：

1、只能买卖最多两次，就分段，可惜方向错了，就差一点点，想得还是不够多。

下面是别人的代码：

    int maxProfit(vector<int> &prices) {
    	int length = prices.size();
    	if (length <= 1)
    		return 0;
    	int left[length], right[length];
    	memset(left, 0, sizeof(int) * length);
    	memset(right, 0, sizeof(int) * length);
    	int min = prices[0];
    	for (int i = 1; i < length; i++) {
    		left[i] = prices[i] - min > left[i - 1] ? prices[i] - min : left[i - 1];
    		min = prices[i] < min ? prices[i] : min;
    	}
    	int max = prices[length - 1];
    	for (int i = length - 2; i >= 0; i--) {
    		right[i] = max - prices[i] > right[i + 1] ? max - prices[i] : right[i + 1];
    		max = prices[i] > max ? prices[i] : max;
    	}
    	int profit = 0;
    	for (int i = 0; i < length; i++)
    		profit = left[i] + right[i] > profit ? left[i] + right[i] : profit;
    	return profit;
    }

参考网页：参考代码

要多尝试其他的方法！！！