1. 最長遞增子序列?

我們來看一下我們的貪心策略體現在哪里？？？

我們來總結一下：

我們在考慮最長遞增子序列的長度的時候，其實并不關心這個序列長什么樣子,我們只是關心最后一個元素是誰。這樣新來一個元素之后， 我們就可以判斷是否可以拼接到它的后面。因此，我們可以創建一個數組，統計長度為 x 的遞增子序列中，最后一個元素是誰。為了盡可能的讓這個序列更長，我們僅需統計長度為x的所有遞增序列中最后一個元素的「最小值」。此時我們來算一下時間復雜度，首先我們要遍歷整個數組，其次我們還要遍歷長度為x的序列，那么此時的復雜度是O(N2)，統計的過程中發現，數組中的數呈現「遞增」趨勢，因此可以使用「二分」來查找插入位置。

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> ret;ret.push_back(nums[0]);for(int i = 1; i < nums.size(); i++){if(nums[i] > ret.back()){ret.push_back(nums[i]);// 如果能接在最后?個元素后?，直接放}else{// 使用二分找到插入位置int left = 0;int right = ret.size() - 1;while(left < right){int mid = (left + right) / 2;if(ret[mid] < nums[i]){left = mid + 1;}else{right = mid;}}ret[left] = nums[i];// 放在 left 位置上}}return ret.size(); }
};

2. 遞增的三元子序列?

我們會發現這道題目就是最遞增子序列的簡化版，因此我們可以使用貪心的思想，找到最長子序列然后判斷長度是否大于3即可解決，但是實際上我們不需要使用二分算法，因為我們只需要求出長度為3的子序列，僅需兩次比較就可以找到插入位置，同時不用一個數組存數據，僅需兩個變量即可，此時的時間復雜度為O(N).

直接來上代碼：

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int a = nums[0];int b = INT_MAX;for(int i = 0; i < nums.size(); i++){if(nums[i] > b) return true;else if(nums[i] > a) b = nums[i];else a = nums[i];}return false;}
};

3. 最長連續遞增序列

這個題目比較簡單，找到以某個位置為起點的最長連續遞增序列之后（設這個序列的末尾為 j 位置），接下來直接以 j + 1 的位置為起點尋找下?個最長連續遞增序列，我們沒有必要從i + 1位置進行尋找，因為 i 位置找到的序列肯定是最長的！！！

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {int ret = 0;int i = 0;while(i < nums.size()){int j = i + 1;// 找到遞增區間的末端while(j < nums.size() && nums[j] > nums[j-1]){j++;}ret = max(ret,j - i);// 直接在循環中更新下?個位置的起點i = j; // 貪心}return ret;}
};

4. 買賣股票的最佳時機

首先我們看到這道題目，第一想到的肯定是暴力枚舉，我們可以依次枚舉兩個位置，然后進行相減，最后保存相減出來的最大值即可，但是這樣的復雜度就是O(N2)的，此時我們就可以進行優化，我們在枚舉賣出價格時候，并不用將前面買入的股票的價格依次枚舉，我們只需要找到其中的最小值即可，這一個點就體現出來貪心的策略，由于只能交易?次，所以對于某?個位置 i ，要想獲得最大利潤，僅需知道前?所有元素的最小值。然后在最小值的位置「買入」股票，在當前位置「賣出」股票即可。

class Solution {
public:int maxProfit(vector<int>& prices) {int prevmin = INT_MAX;int ret = 0; // 記錄最終結果for(int i = 0; i < prices.size(); i++){// 先更新結果ret = max(prices[i] - prevmin, ret);// 再更新最小值if(prices[i] < prevmin)prevmin = prices[i];}return ret;}
};

5. 買賣股票的最佳時機Ⅱ

由于可以進行?限次交易，所以只要是?個「上升區域」，上升區間一定是穩賺的，我們就把利潤拿到手就好了，這就是貪心策略。

?解法一：雙指針

class Solution {
public:int maxProfit(vector<int>& prices) {int ret = 0;for(int i =0 ; i < prices.size(); ){int j = i;while(j + 1 < prices.size() && prices[j + 1] > prices[j]){j++; // 尋找上升的區間}ret += prices[j] - prices[i];i = j + 1;}return ret;}
};

?解法二：拆分交易，只要今天的股票的價格大于昨天，就可以累計到利潤上

class Solution {
public:int maxProfit(vector<int>& prices) {int ret = 0;for(int i = 1; i < prices.size(); i++){if(prices[i] > prices[i - 1])ret += prices[i] - prices[i - 1];}return ret;}
};