c++给定一个长度为 n 的序列 {an}，求其最长上升子序列长度。O(n logn)

可以使用二分查找和动态规划的思想，时间复杂度为 O(n logn)。

具体的做法是，维护一个数组 dp，dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。初始时，dp[1] = a[1]，其余为 INF。然后从 i = 2 到 n，对于每个 a[i]，在 dp 数组中查找第一个大于等于 a[i] 的元素 dp[j]，将其替换为 a[i]。如果不存在这样的元素，说明 a[i] 大于所有的 dp[j]，此时应该将 dp 数组的长度加 1，即 dp[len+1] = a[i]，其中 len 表示当前 dp 数组的最大下标。最终，dp 数组的长度就是最长上升子序列的长度。

代码如下：

const int INF = 0x3f3f3f3f;
int dp[N], len = 1; // dp 数组和最大下标 len
dp[1] = a[1];
for (int i = 2; i <= n; ++i) {
    if (a[i] > dp[len]) { // 情况 1
        dp[++len] = a[i];
    } else { // 情况 2
        int pos = lower_bound(dp + 1, dp + len + 1, a[i]) - dp;
        dp[pos] = a[i];
    }
}

其中 lower_bound 函数可以使用 STL 中的 lower_bound，也可以手写实现。

相关问题

给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

题目描述

给定N个数的序列a1,a2,…,aN，定义一个数对(ai,aj)为“重要逆序对”的充要条件为i<j且ai>2aj。求给定序列中“重要逆序对”的个数。

输入格式
第一行一个整数N(1≤N≤105)，表示序列中数的个数。

第二行N个整数a1,a2,…,aN(1≤ai≤109)。

输出格式
输出一个整数，表示给定序列中“重要逆序对”的个数。

样例

输入样例：
5
1 3 2 4 5
输出样例：
2

算法1

(归并排序) $O(nlogn)$

我们借鉴归并排序中的分治思路，假设当前要排序的区间为[l,r]，可以将其拆分成两个区间：[l,mid]和[mid+1,r]，排序后合并。

我们可以在合并时统计重要逆序对的数量。此时我们已经分别求出了[l,mid]和[mid+1,r]中的重要逆序对数量，因此[l,mid]和[mid+1,r]中分别分别排序后的数组已经是有序的。

接下来，在合并[l,mid]和[mid+1,r]的过程中，假设当前[l,mid]中的剩余元素为[i,j]，[mid+1,r]中的剩余元素为[k,l']，其中[mid+1,r]中的前k-1个元素已经入到合并后的数组中，剩下的为[k,l']。

当我们将[l,mid]中的某个元素ai加入合并后的数组时，记下另一个区间中所有大于2ai的元素数量cnt，那么[cnt,mid+1]中的元素均为重要逆序对。

因为[mid+1,r]中的元素已经是有序的，因此在其后续的数中也不可能再有重复的重要逆序对。此时我们移动到下一个[l,mid]中的元素，同样记下另一个区间中所有大于2ai的元素数量cnt。

我们依此类推，最后统计出[l,mid]中的所有元素与[mid+1,r]中的重要逆序对数量之和即为答案。

时间复杂度

排序的时间复杂度是O(nlogn)，在合并时统计重要逆序对的数量的时间复杂度是O(n)，因此总时间复杂度是O(nlogn)。

C++ 代码

算法2

(线段树) $O(nlogn)$

线段树中每个节点表示[l,r]区间中每个元素的重要逆序对数量。

考虑每个节点如何合并成父节点的值。

假设一个节点表示的区间为[l,r]，左右子节点分别表示的区间为[l,mid]和[mid+1,r]，则当前节点表示的重要逆序对有三个来源：

子节点中来自[l,mid]的重要逆序对数量。

子节点中来自[mid+1,r]的重要逆序对数量。

跨越[l,mid]和[mid+1,r]的重要逆序对数量。该数量可以通过枚举[l,mid]中的每个元素ai，统计[mid+1,r]中所有大于2ai的元素数量cnt，那么在该区间中对该元素的贡献就是cnt。

为了方便合并，对于每个节点中的信息，我们需要维护三个信息：

划分区间[l,r]。

[l,r]中的元素按照从小到大的顺序排序后得到的数组。

[l,r]中重要逆序对数量。

这里我们仅讨论如何维护第一个和第三个信息，第二个信息可以在插入过程中维护。

由于线段树每个节点表示的区间长度为1，因此我们可以直接用一个整数数组来存储每个节点的信息。对于节点l，其左右子节点分别为2l和2l+1，父节点为l/2。

时间复杂度

每次查询树中的最大值需要O(logn)的时间，共需要查询n次，因此总时间复杂度是O(nlogn)。

C++ 代码

求解众数问题，给定一个整数序列，给定一个整数序列，每个元素出现的次数称为重数，重数最大的元素称为众数，编写一个实验程序对递增有序序列求众数。例如：a={1,2,2,2,3,3,5,6,6,6,6}，其众数为6，重数为4。 求解思路为：解:求众数的方法有多种,这里采用分治法求众数。 用全局变量num和maxcnt分别存放α的众数和重数(maxcnt的初始值为0)。对于至少含有一个元素的序列a[low..high],以中间位置mid为界限,求出a[mid]元素的重数cnt,即 a[left.. right]均为a[mid],cnt- right—left＋1,若cnt大于maxcnt,置num-a[midJ，maxcnt- cnt。然后对左序列a[low..left-1]和右序列a[right+1..high]递归求解众数，完整代码c++求

下面是采用分治法求解众数的完整代码实现（C++ 版本）：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int num = 0, maxcnt = 0;
        divide(nums, 0, nums.size() - 1, num, maxcnt);
        return num;
    }

private:
    void divide(vector<int>& nums, int left, int right, int& num, int& maxcnt) {
        if (left == right) {
            num = nums[left];
            maxcnt = 1;
            return;
        }
        int mid = left + (right - left) / 2;
        int left_num = 0, left_maxcnt = 0;
        divide(nums, left, mid, left_num, left_maxcnt);
        int right_num = 0, right_maxcnt = 0;
        divide(nums, mid + 1, right, right_num, right_maxcnt);
        int cnt = 0;
        if (left_num == right_num) {
            num = left_num;
            maxcnt = left_maxcnt + right_maxcnt;
            return;
        }
        for (int i = left; i <= right; i++) {
            if (nums[i] == left_num) {
                cnt++;
            } else if (nums[i] == right_num) {
                cnt--;
            }
        }
        if (cnt > 0) {
            num = left_num;
            maxcnt = left_maxcnt + cnt;
        } else {
            num = right_num;
            maxcnt = right_maxcnt - cnt;
        }
    }
};

该方法的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)。