C++ Minimum Array Jumps and Oscillating Subsequence

Posted on Feb 21, 2026 in Computer Engineering

C++ Minimum Array Jumps and Oscillating Subsequence

Code samples: two C++ routines: one to compute the minimum number of jumps to reach the end of an array, and another to compute the longest oscillating indexed subsequence using a segment tree and coordinate compression.

Minimum Array Jumps (C++)

The following function returns the minimum number of jumps required to reach the last index of an array where each element denotes the maximum jump length from that position. It returns -1 if the end is not reachable.

// Min array jumps
int minimumJumps(const vector& a) {
    int n = static_cast(a.size());
    if (n == 1) return 0;
    if (a[0] == 0) return -1;

    int jumps = 0;
    int currentEnd = 0;
    int farthest = 0;

    for (int i = 0; i < n - 1; ++i) {
        farthest = max(farthest, i + a[i]);
        if (farthest <= i) return -1;
        if (i == currentEnd) {
            ++jumps;
            currentEnd = farthest;
            if (currentEnd >= n - 1)
                break;
        }
    }
    return (currentEnd >= n - 1) ? jumps : -1;
}

Oscillating Indexed Subsequence (C++)

The following implementation finds the maximum length of an oscillating indexed subsequence. It uses coordinate compression, two segment trees (for even and odd values), and a small pending queue to delay updates for the required index spacing.

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

struct SegTree {
    int n;
    vector st;
    SegTree(int _n = 0) { init(_n); }
    void init(int _n) {
        n = max(1, _n);
        st.assign(4 * n, INT_MIN);
    }
    void update(int p, int val, int node, int l, int r) {
        if (l == r) { st[node] = max(st[node], val); return; }
        int mid = (l + r) >> 1;
        if (p <= mid) update(p, val, 2 * node, l, mid);
        else         update(p, val, 2 * node + 1, mid + 1, r);
        st[node] = max(st[2 * node], st[2 * node + 1]);
    }
    void update(int p, int val) { update(p, val, 1, 0, n - 1); }
    int query(int ql, int qr, int node, int l, int r) const {
        if (ql > r || qr < l) return INT_MIN;
        if (ql <= l && r <= qr) return st[node];
        int mid = (l + r) >> 1;
        return max(query(ql, qr, 2 * node, l, mid),
                   query(ql, qr, 2 * node + 1, mid + 1, r));
    }
    int query(int l, int r) const {
        if (l > r) return INT_MIN;
        return query(l, r, 1, 0, n - 1);
    }
};

struct Pending {
    int idx;
    int pos;
    int len;
    bool even;
};

int get_max_length(int N, const vector& Arr)
{
    if (N == 0) return 0;
    vector comp = Arr;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    auto compress = [&](int x) {
        return (int)(lower_bound(comp.begin(), comp.end(), x) - comp.begin());
    };

    int M = (int)comp.size();
    SegTree evenSeg(M), oddSeg(M);
    queue q;
    vector dp(N, 1);
    int bestAns = 1;

    for (int i = 0; i < N; ++i) {
        while (!q.empty() && q.front().idx <= i - 3) {
            auto p = q.front(); q.pop();
            if (p.even) evenSeg.update(p.pos, p.len);
            else        oddSeg.update(p.pos, p.len);
        }

        int pos = compress(Arr[i]);
        int best = INT_MIN;
        best = max(best, evenSeg.query(pos + 1, M - 1));
        best = max(best, oddSeg.query(0, pos - 1));
        if (best != INT_MIN) dp[i] = best + 1;
        bestAns = max(bestAns, dp[i]);

        bool isEven = (Arr[i] % 2 == 0);
        if ((dp[i] & 3) == 3) {
            q.push({i, pos, dp[i], isEven});
        } else {
            if (isEven) evenSeg.update(pos, dp[i]);
            else        oddSeg.update(pos, dp[i]);
        }
    }
    return bestAns;
}

Notes

Minimum jumps uses a greedy, linear scan tracking current reach and farthest reachable index.
Oscillating subsequence uses coordinate compression and two segment trees to store best lengths for even and odd values, plus a pending queue for delayed updates.

C++ Minimum Array Jumps and Oscillating Subsequence