学步园

本解法启发自http://blog.csdn.net/pickless/article/details/12034365， 以下文字部分亦转自该文

O(n^2)的算法很容易想到：

找寻一个点j，将原来的price[0..n-1]分割为price[0..j]和price[j..n-1]，分别求两段的最大profit。

进行优化：

对于点j+1，求price[0..j+1]的最大profit时，很多工作是重复的，在求price[0..j]的最大profit中已经做过了。

类似于Best Time to Buy and Sell Stock，可以在O(1)的时间从price[0..j]推出price[0..j+1]的最大profit。

但是如何从price[j..n-1]推出price[j+1..n-1]？反过来思考，我们可以用O(1)的时间由price[j+1..n-1]推出price[j..n-1]。

最终算法：

数组l[i]记录了price[0..i]的最大profit，

数组r[i]记录了price[i..n]的最大profit。

已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。

最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution 
{
public:
//注释部分为 O(n^2)的解法 
/*
	int subProfit(vector<int> &p, int lhs, int rhs)
	{
		int len = rhs - lhs + 1;
		
		int minv = p[lhs], profit = 0;
		for(int i = lhs + 1; i <= rhs; ++i)
		{
			if(profit < p[i] - minv)
				profit = p[i] - minv;
			if(p[i] < minv)
				minv = p[i];
		}
		return profit;
	}
    int maxProfit(vector<int> &prices) 
	{
        int len = prices.size();
		if(len < 2)
			return 0;

		int maxv = 0;
		
		for(int i = 1; i < len - 1; ++i)
		{
			int tmp = subProfit(prices, 0, i) + subProfit(prices, i+1, len-1);
			if(maxv < tmp)
				maxv = tmp;	
		}
		return maxv;
    }*/
    
    int maxProfit(vector<int> &prices) 
	{
        int len = prices.size();
		if(len < 2)
			return 0;
				
		int *l = new int[len];              //用以记录 prices[0 ~ i] 最大的收益 
		int *r = new int[len];				//用以记录 prices[i ~ len -1] 最大的收益 
		memset(l, 0, sizeof(int) * len);
		memset(r, 0, sizeof(int) * len);
		
		int minv = prices[0];
		for(int i = 1; i < len; ++i)
		{
			l[i] = max(prices[i] - minv, l[i-1]);
			minv = min(prices[i], minv);
		}
		
		int maxv = prices[len - 1];
		for(int j = len - 2; j >= 0; --j)
		{
			r[j] = max(maxv - prices[j], r[j + 1]);
			maxv = max(prices[j], maxv);
		}
		
		int re = 0;
		for(int i = 0; i < len; ++i)
		{
			re = re > l[i] + r[i] ? re : l[i] + r[i];
		}
		
		delete[] l;
		delete[] r;
		
		return re;
    }
};

int main(void)
{
	/*
int a[] = {
		3, 7, 8, 2, 9, 6, 1, 10, 5
	};*/

//int a[] = {
//		4, 2, 1
//	};
//	

int a[] = {
		1, 2, 4 
	};
	
	int len = sizeof(a) / sizeof(int);
	vector<int> v(a, a + len);
	
	Solution s;
	
	cout << s.maxProfit(v) << endl;
	
	return 0;
}