一、排序子序列

題目解析

一個數組的連續子序列，如果這個子序列是非遞增或者非遞減的；這個連續的子序列就是排序子序列。

現在給定一個數組，然后然我們判斷這個子序列可以劃分成多少個排序子序列。

例如：1 2 3 2 2 1 可以劃分成 1 2 3和2 2 1兩個排序子序列

算法思路

對于這道題，思路就很簡單了：

暴力解法

從0位置開始遍歷，尋找一段連續子序列，直到這一段子序列不滿足排序子序列的條件，即找到了一個排序子序列；

然后繼續從上次遍歷結束位置接著遍歷數組，尋找下一個子序列。

貪心優化：

當我們遍歷到數組中數值相同的區域時，我們要知道，要找的子序列是非遞增或者非遞減的；

所以這一段相等的序列，我們可以加到前面或者后面的任意序列中。

所以我們在遇到數值相等的子序列時，繼續向后遍歷即可。

但是這樣我們會發現兩個問題：

1. 如果數組剛開始位置的數據是相等的，我們不知道這段子序列是非遞增的還是非遞減的；
2. 我們在遍歷過程中會用到下一個位置的值來判斷是非遞增還是非遞減，那最后一個位置該怎么辦？

對于數組開頭的相等子序列，我們可以直接跳過，因為這一段相等的序列可以加到后面的子序列中；

而對于最后一個位置，如果它不能和前面序列組成一個排序子序列，那就只能讓它自己組成一個排序子序列了。

代碼實現

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int n;
int main() {cin >> n;for (int i = 0; i < n; i++)  cin >> arr[i];int ret = 0;for (int i = 0; i < n; i++) {if (i == n - 1) { //數組最后一個位置ret++;break;}if (arr[i] < arr[i + 1]) {//非遞增while (i < n && arr[i] <= arr[i + 1])i++;ret++;} else if (arr[i] > arr[i + 1]) {//非遞減while (i < n && arr[i] >= arr[i + 1])i++;ret++;} else {//數組開始位置的相等子序列while (i < n && arr[i] == arr[i + 1])i++;}}cout << ret << endl;return 0;
}

二、消減整數

題目解析

這道題給定一個正整數H，然后從1開始減，第一次減去1，之后每一次減去的數要么和上一次相等，要么是上一次的兩倍；

簡單來說就是：h每次減去一個數，x起始是1；之后每一h減去x或者2*x（x表示上次減去的數）。

現在，最少需要幾次才能將h減到0。

算法思路

對于這道題，暴力解法：

h每次減去x或者2*x，讓它一值減，直到h減到0或者<0。

簡單來說就是分情況討論：第一次減去1，之后分別考慮減去x和減去2*x的情況。

這樣時間復雜度和空間復雜度都太大了；并且h每一次減也不一定會恰好等于0。

貪心優化：

這道題要我們求的是將x減到0的最少次數；

那如果我們的h減去某一個數是無法減到0的，那我們就不用去考慮它了；

所以，我們現在要考慮的是，h減的過程中，減去x能否減到0；減去2*x能否減到0。

這個也非常容易判斷了，如果h是x的整數倍，那減去x就肯定可以減到0；如果h是2*x的整數倍，那減去2*x就也能減到0。

現在有一個問題，如果h既是x的倍數，也是2*x的倍數， 那是減去x還是2*x呢？

很顯然是減去2*X，因為我們要求的是h減到0的最小次數，那可以是減去大的數次數更小啊。

所以我們整體思路就出來了，在減的過程中，判斷h是2*x的倍數，如果是就減去2*x；如果不是就減去x。

代碼實現

#include <iostream>
using namespace std;
int main()
{int t;cin>>t;while(t--){int n;cin>>n;n--;//第一次減去1int ret = 1,x = 1;while(n){if(n % (2*x) == 0)x*=2;n-=x;ret++;}cout<<ret<<endl;}return 0;
}

三、最長上升子序列(二)

題目解析

對于這道題，給定一個數組，然后我們要找到這個數組中最長嚴格上升子序列的長度；

嚴格上升子序列：一個數組刪掉其中一些數（可以不刪）之后，形成的新數組它是嚴格上升（非遞減）的。

簡單來說就是：一個數組的子序列，這個子序列是嚴格上升的。

現在我們要找到所有上升子序列中長度最長的子序列；然后返回它的長度。

算法思路

對于這道題，一眼看起，可以說毫無思路；這該如何去找啊？

細細看來：

我們要找所有嚴格上升的子序列，當我們遍歷到某一個位置時，我們要知道這個位置的數據和前面位置的數據是否能夠形成嚴格上升的子序列；所以我們就要知道這個位置前面有多少個嚴格上升的子序列，這個位置的數據能放到哪些子序列當中去？

所以我們就要記錄：當前所有的嚴格上升子序列，以及子序列中的元素。

那我們如何去記錄所有的嚴格上升子序列呢？

當遍歷到一個位置時：

這個位置如果是大于等于前面所有位置的，那我們可以把這個位置的元素放到任意一個子序列的后面形成一個新的子序列；

但是，我們沒有必要去把這個元素放到每一個子序列的后面形成新的子序列。

加入前面有子序列1、1,2、1,2,4，當前位置數據是7，我們可以形成1,7、1,2,7和1,2,4,7三個新的子序列；但是我們可以發現長度為2的子序列有兩個1,2和1,7，我們有必要把這兩個長度一樣的子序列都記錄下來嗎？

很顯然是不需要的，我們只需要記錄長度為n的子序列它最后一個元素最小的子序列即可

所以，我們只需要按長度n（1,2,3...n）記錄子序列即可。

那問題又來了，我們要記錄子序列中的所有元素嗎？

比如1、1,2、1,2,4、1,2,4,7，我們要記錄子序列中的所有元素嗎？

當然也是沒有必要的；當我們遍歷一個位置時，我們只需要判斷這個位置的能否和前面的子序列組成新的子序列；我們不需要關心這個子序列是什么，所以我們只需要保存子序列最后一個位置的元素即可。

那現在還有一個問題：遍歷一個位置時，它可以與前面子序列形成新的子序列，但是長度不是最大的怎么辦？

簡答來說：現在有子序列1、1,2、1,2,4、1,2,4,7四個子序列，現在遍歷到某一個位置，這個位置的值是3；

它可以和1形成1,3但是最后一個元素是3是大于1,2的最后一個元素2的，我們可以不用考慮。

它可以和1,2形成1,2,3，它最后一個元素3是小于1,2,4最后一個元素4的，我們就要修改長度為3的子序列，將4修改成3。

OK啊，現在大致明白了這道題如何去解決；

但是我們要遍歷一遍數組，而且還要去判斷一個某一個位置是否能和前面子序列形成新的子序列，形成新的子序列是否比之前的子序列更好；那就要存放每一個長度的子序列對應的最后一個元素的值；時間復雜度那不就是O(n^2)了，題目明確要求時間復雜度是O(n log N)啊。

二分查找

所以這里我們要使用二分算法去優化查找。

當我們遍歷到一個位置時，當這個位置的值是>=dp[pos]（大于長度最大的子序列的最后一個位置），它可以和長度最大的子序列形成一個新的子序列，長度就是pos+1，直接新增一個位置即可（dp[pos+1] = x）。

但是如果這個位置的值是小于長度最大的子序列的最后一個位置，它可能可以和前面的某一個子序列形成新的子序列，而形成新的子序列的最后一個位置的值，一定是小于等于之前該長度的子序列最后一個位置的值的。

所以我們就要找到這個子序列；

我們按暴力查找它的時間復雜度是O(n)；但是我們仔細思考可以發現，我們存放的是長度為n的子序列的最后一個位置的值，那這個數組dp是不是就是非遞減的了？

所以我們就可以使用二分查找來搜索這個子序列，而我們要找的也就是>=當前位置的值的區間左端點。

代碼實現

class Solution {public:int dp[100001];int pos = 0;int LIS(vector<int>& a) {for (auto& e : a) {if (pos == 0 || e >= dp[pos])dp[++pos] = e;else {int l = 1, r = pos;while (l < r) {int mid = l + (r - l) / 2;if (dp[mid] >= e)r = mid;elsel = mid + 1;}dp[l] = e;}}return pos;}
};

到這里，本篇文章內容就結束了。
繼續加油啊！！！