#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*問題:Contributors: AdminSay 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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.Example 1:Input: [7, 1, 5, 3, 6, 4]Output: 5max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)Example 2:Input: [7, 6, 4, 3, 1]Output: 0In this case, no transaction is done, i.e. max profit = 0.分析:給定一個數組，模擬股票價格，要求獲取最大利潤。也就是從數組中選取兩個元素,并且滿足較小的元素在前面，較大的元素在后面，求這樣一個差值最大的兩個元素。如果數組降序，直接返回利潤為0。問題的關鍵在于不能簡單的去找到最小值和最大值，必須滿足較小的元素在前面，較大的元素在后的情況。因此，如果設定一個指向較小元素指針low從前向后遍歷，設定一個指向較大元素的指針high從后向前遍歷。假設數組為A。如果A[low] >= A[high]，不能這樣做。指針的走位收到其他元素的影響。這個應該是動態規劃。如果采用暴力破解，羅列每個買入股票的位置和賣出股票的位置，時間復雜度就是O(n^2)如果采用以當前元素為中心，分別向左和向右擴散的方式，向左找到比自己最小的元素，向右找到比自己最大的元素，然后比較差值時間復雜度也是O(n^2)輸入:67 1 5 3 6 457 6 4 3 142 1 7 452 4 1 7 11輸出:50610超時，說明有比O(n^2)更好的方法。參考分治的情況。將數組劃分成兩部分。設數組為A[1...n]1】如果左邊和右邊都求出了有差值，記結果分別為lDiff = lMax - lMin,rDiff = rMax - rMin如果lMax <= rMin,diff=rMax - lMin否則，diff=max(lMax , rMax) - lMin,diff=max(diff ,lDiff, rDiff)2】左邊和右邊都沒有求出差值，說明都是降序，易錯，左右都無效，不能直接返回0。左邊是降序，右邊是降序，找出左邊最小和右邊最大，如果左邊最小 < 右邊最大，返回結果3】左邊求出差值，右邊沒有求出，說明右邊是降序排列，diff=max(lMax,右邊最大元素)-lMin,右邊最大元素是右邊序列中第一個元素4】左邊沒有求出差值，右邊求出差值，左邊降序，左邊序列中最后一個元素最小diff=rMax - min(rMin , 左邊序列最小元素)報錯:2 1 7 4，我的結果是0，預期結果是6。Input:[2,4,1,7,11] ，Output:9 ，Expected:10 發現漏掉了對1和7,11的比較，證明該分治算法是有問題的{1, 7, 4, 11}, if he gives {0, 6, -3, 7},關鍵:1 leecode解法:https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution/16一直記錄從初始到當前元素的最小值，和最大利潤(初始為0)，如果當前元素 > 最小值，計算新的利潤，如果新的利潤 > 當前最大利潤，更新最大利潤。沒想到可以通過記錄一個最小元素來解決該問題，最小元素解決了需要雙層循環的問題*/class Solution {public:    int maxProfit(vector<int>& prices) {        if(prices.empty())		{			return 0;		}		int size = prices.size();		int minPrice = INT_MAX;		int profitMax = 0;		for(int i = 0 ; i < size ; i++)		{			if(prices.at(i) < minPrice)			{				minPrice = prices.at(i);			}			else			{				profitMax = max(profitMax , prices.at(i) - minPrice);			}		}		return profitMax;	}};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 int result = solution.maxProfit(nums);		 cout << result << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}