題目描述
給定一個數(shù)組炊汤，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設(shè)計一個算法來計算你所能獲取的最大利潤豫柬。
注意你不能在買入股票前賣出股票告希。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出烧给，最大利潤 = 6-1 = 5 燕偶。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0础嫡。
題目解答
思路就是采用動態(tài)規(guī)劃的思想杭跪，來對此題進行求解
初版代碼：
int maxProfit(int* prices, int pricesSize) {
if (pricesSize == 0 || pricesSize == 1)
return 0;
int j = 0, max = 0, min = prices[0], ret[pricesSize];
for (int i = 1; i < pricesSize; i++) {
ret[j++] = max > prices[i] - min ? max : prices[i] - min;
max = ret[j-1]; // 前i天的最大利潤
if (min > prices[i])
min = prices[i]; // 更新前i天的最低價格
}
return max;
}
然后經(jīng)過研究，我們可以發(fā)現(xiàn)并不需要申請一個多余的數(shù)組驰吓，直接更新 max 的值即可涧尿，于是就有了改進版代碼：（也是C語言提交最快的示例代碼）
int maxProfit(int* prices, int pricesSize) {
if (prices == NULL || pricesSize <=0)
return 0;
int max = 0, min = prices[0];
for (int i = 1; i < pricesSize; i++) {
if (prices[i] - min > max)
max = prices[i] - min;
if (prices[i] < min)
min = prices[i];
}
return max;
}
然后，我們想進一步優(yōu)化檬贰，將第一行的判斷去掉姑廉，無需判斷傳入的數(shù)組是否為空，那么我們可以直接將min 省略掉翁涤，也就是最終版代碼：（C語言4ms示例代碼）
int maxProfit(int* prices, int pricesSize) {
int max = 0,realmax = 0;
for(int i = 1;i < pricesSize;i++) {
max += prices[i] - prices[i-1];
if(max < 0)
max = 0;
if(max > realmax)
realmax = max;
}
return realmax;
}
即桥言，使用realmax 記錄全程中的最大利潤值，利用 max 來作為過程中累計的最大值葵礼，當(dāng) max 為 0 之后直接將值舍棄号阿。
