動态規劃算法（微軟一面筆試題：股票交易，O(N)時間複雜度O(1)空間複雜度）

1.  此問題簡化為：求數組中兩個元素差的最大值（後面的元素減去前面的元素）
2. 自從暑假面試被鄙視之後，回來就經常想這個問題，到今天應該快兩個月了。在這個下午，我又拿出草稿紙，總算找到了思路，把它給搞定了。就像一個心願一樣，完結了。
3. 問題是這樣的，如同題目：原題就不贅述了，化簡之後的問題就是在數組中找到兩個元素，計算後面的元素減去前面的元素的差。求出所有差的最大值。（你可以認為你在炒股票，買入價格和賣出價格就是你的盈利）
4. 當時想到的方法是，如果一遍周遊這個數組，找到MAX,MIN元素，如果恰好，MAX在MIN的後面，這個問題就解決了，關鍵是如果這種情況不出現怎麼辦，我給出了遞歸的方法，回來自己想想發現不行，遞歸不靠譜，對一些測試用例來說很難有很高的效率。
5. 潛意識告訴我，求數組中連續元素的最大和的方法對這個問題有很大的啟發，那個問題在本部落格中已經解決過了，而且我反複做了兩遍，太好了。那個問題的解決思路是将全部元素的問題，看成是從兩個元素大小的數組開始的問題。當這個包含兩個元素的問題解決了，那麼加一個新的元素會造成什麼影響？要改變哪些值？每次都添加一個元素，每次都将這些可能的改變考慮進來，這樣就能做到周遊整個數組的時候，問題就解決了。達到了最快的速度O（N）
6. 有了上面的思路，這個問題居然更簡單，其實作如下：

int max_difference(const vector<int>& arr)
{
	if (arr.size()>=2)
	{
		int MIN=min(arr[0],arr[1]);
		int MAX_DIFFERENCE=arr[1]-arr[0];//第一個被求出的內插補點，暫時作為最大的內插補點
		for (vector<int>::size_type i=2;i<arr.size();i++)
		{
			if (arr[i]-MIN>MAX_DIFFERENCE)
			{
				MAX_DIFFERENCE=arr[i]-MIN;
			}
			if (arr[i]<MIN)
			{
				MIN=arr[i];//影響新的內插補點的關鍵在于已經找到的目前的最小元素是誰，隻要将目前值減去這個最小元素就能更新MAX_DIFFERENCE
			}
		}
		return MAX_DIFFERENCE;
	}
	else
	{
		cout<<"size of arr is too small";
		return 0;
	}
	
}
void give_result(int a[],int n)
{
	vector<int> arr(a,a+n);
	print(arr.begin(),arr.end());
	print(max_difference(arr));
}
int main( void ) 
{
	int a0[]={7,9,10};
	give_result(a0,3);
	int a1[]={10,9,7};
	give_result(a1,3);
	int a[]={3,10,1,9};
	give_result(a,4);
	int a2[]={3,9,2,10,1,8};
	give_result(a2,6);
	return 0;
}
           

其輸出結果每兩行作為一組，第一行為要考慮的數組的全部元素，第二行為其max_difference的結果。

陸陸續續的做了不少筆試題，也感覺收獲很大，但畢竟做的不夠，這個是第一個用已經掌握的技巧解決的。感覺算法強大！！

細心的讀者還會發現，本文中的代碼使用了vector的逆序疊代器。以前做過類似算法要求的周遊使用正向疊代器總感覺别扭，忽然想起了逆序疊代器。發現真的适合這種情形。