简单的数组题，将一个序列分成两个不重合的子序列，子序列中最大值与最小值之差不超过K

第一行为两个整数n和k（0≤k≤109）
接下来是n行，每行一个正整数，表示序列值，保证均为正整数且不超过109。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int len[N];    //以i开头的最长子序列
int maxlen[N]; //i右侧的最长子序列
int w[N];
int n, k;

int find(int i) {
    //找到与w[i]之差小于等于k最大元素
    int l = i, r = n - 1;
    int target = w[i] + k;

    while (l < r) {
        int mid = (l + r + 1) / 2;      //+1避免死循环
        if (w[mid] == target) {
            return w[mid];
        }
        else if (w[mid] > target) {
            r = mid - 1;
        }
        else {
            l = mid;
        }
    }

    return w[l];
}

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n >> k;

    unordered_map<int, int> last;   //记录一个数的最后出现的位置

    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        w[i] = a;
    }
    sort(w, w + n);

    for (int i = 0; i < n; i++) {
        last[w[i]] = i;
    }

    for (int i = 0; i < n; i++) {
        int r = last[find(i)];   //找到最后一个满足条件的数的索引
        len[i] = r - i + 1;
    }

    for (int i = n - 1; i >= 0; i--) {
        maxlen[i] = max(len[i], maxlen[i + 1]);
    }

    int ans = 0;

    for (int i = 0; i < n; i++) {
        //以i开头的最长子序列 + 该序列右边的最长子序列
        ans = max(ans, len[i] + maxlen[i + len[i]]);
    }

    cout << ans;

    fclose(stdin);
    fclose(stdout);
    return 0;
}