1. 題目
1.1 英文題目
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
1.2 中文題目
給定一個陣列，它的第 i 個元素是一支給定股票第 i 天的價格，
如果你最多只允許完成一筆交易（即買入和賣出一支股票），設計一個演算法來計算你所能獲取的最大利潤，
注意你不能在買入股票前賣出股票，
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| prices = [7,1,5,3,6,4] | 5 |
| prices = [7,6,4,3,1] | 0 |
1.4 約束條件
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
2. 實驗平臺
IDE：VS2019
IDE版本：16.10.1
語言：c++11
3. 分析
這一題最簡單粗暴的方法就是窮舉列舉，代碼為：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxprofit = 0;
for (int i = 0; i < prices.size() - 1; i++)
{
for (int j = i + 1; j < prices.size(); j++)
{
int temp = prices[j] - prices[i];
if ( temp > maxprofit)
{
maxprofit = temp;
}
}
}
return maxprofit;
}
};
這樣做只適用于資料較少的情形，而對于大資料很容易造成超時現象，那么能不能進行優化一下，我想到了雙指標法，快指標負責遍歷整個陣列，當快指標的值小于等于慢指標的值時，將慢指標指向快指標指向的位置，新代碼如下：
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ans;
for(int i = 0; i < rowIndex + 1; i++)
{
vector<int> temp(i + 1);
temp[0] = temp[i] = 1;
for(int j = 1; j < i; j++)
{
temp[j] = ans[j - 1] + ans[j];
}
ans = temp;
}
return ans;
}
};
但是我們提交后發現演算法時間和空間復雜度都沒變，于是我在想還有沒有優化空間，我發現每行計算時都需要重新定義temp，并為其開辟記憶體空間，有待優化，故可以將其提前定義，并在每行計算時重定義temp大小，代碼如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int slow = 0;
int max = 0;
int temp = 0;
for (int quick = 1; quick < prices.size(); quick++)
{
temp = prices[quick] - prices[slow];
if (temp <= 0) slow = quick;
else if (temp > max) max = temp;
}
return max;
}
};
這次性能不錯，在寫這段程式的程序中，我最開始是將temp在for回圈內進行定義并賦值，但是我發現如果把它放在外面定義，可以優化演算法的時間和空間復雜度，于是我想到，變數的定義也是需要消耗時間和空間的，因此最好是提前定義好，也就是盡量減少定義次數，
另外，在題目的solution中我還發現大佬用Kadane's Algorithm進行求解，他的大概思想就是將陣列中相鄰元素的差值（后減去前）重新組成一個陣列，之后對這個求最大子序列和，詳細介紹可以參考：https://blog.csdn.net/shendezhuti/article/details/105114569
代碼如下：
class Solution {
public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288973.html
標籤：C++
下一篇：軟體開發打敗了 80 %的程式員