3915. Maximum Sum of Alternating Subsequence With Distance at Least K

SourceWeekly Contest 499 Q4DifficultyHardRating2288

Description

You are given an integer array nums of length n and an integer k.

Pick a subsequence with indices 0 <= i₁ < i₂ < ... < i_m < n such that:

For every 1 <= t < m, i_t+1 - i_t >= k.
The selected values form a strictly alternating sequence. In other words, either:
- nums[i₁] < nums[i₂] > nums[i₃] < ..., or
- nums[i₁] > nums[i₂] < nums[i₃] > ...

A subsequence of length 1 is also considered strictly alternating. The score of a valid subsequence is the sum of its selected values.

Return an integer denoting the maximum possible score of a valid subsequence.

Example 1:

Input: nums = [5,4,2], k = 2

Output: 7

Explanation:

An optimal choice is indices [0, 2], which gives values [5, 2].

The distance condition holds because 2 - 0 = 2 >= k.
The values are strictly alternating because 5 > 2.

The score is 5 + 2 = 7.

Example 2:

Input: nums = [3,5,4,2,4], k = 1

Output: 14

Explanation:

An optimal choice is indices [0, 1, 3, 4], which gives values [3, 5, 2, 4].

The distance condition holds because each pair of consecutive chosen indices differs by at least k = 1.
The values are strictly alternating since 3 < 5 > 2 < 4.

The score is 3 + 5 + 2 + 4 = 14.

Example 3:

Input: nums = [5], k = 1

Output: 5

Explanation:

The only valid subsequence is [5]. A subsequence with 1 element is always strictly alternating, so the score is 5.

Constraints:

1 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= n

Solutions

Solution 1: Dynamic Programming + Binary Indexed Tree

Thinking

A subsequence DP that enumerates every predecessor at least \(k\) away is \(O(n^2)\) and fails for \(n\le 10^5\). Transfers also require the predecessor to be larger or smaller.

Let \(f[i][0]\) be the best alternating subsequence ending at \(i\) as a valley, and \(f[i][1]\) as a peak. A valley may follow only a larger peak, a peak only a smaller valley, and the indices must differ by at least \(k\).

Two Fenwick trees store prefix maxima of \(f[\cdot][0]\) and suffix maxima of \(f[\cdot][1]\) over the discretized value domain. At index \(i\) we first insert the state at \(i-k\), then query; every predecessor used in a transition is then at least \(k\) away.

State Definition

Let \(f[i][0]\) denote the maximum sum of a valid subsequence ending at index \(i\) where the last element is a valley (the next element must be larger to maintain alternation), and \(f[i][1]\) denote the maximum sum where the last element is a peak (the next element must be smaller).

Transitions

When transitioning, we enumerate a predecessor index \(j\) satisfying \(j \leq i - k\):

State \(f[i][0]\) (valley): transitions from \(f[j][1]\), requiring \(\text{nums}[j] > \text{nums}[i]\), i.e., query the maximum \(f[\cdot][1]\) over the value range \((\text{nums}[i],\ +\infty)\):

\[f[i][0] = \text{nums}[i] + \max\!\left(0,\ \max_{\substack{j \leq i-k \\ \text{nums}[j] > \text{nums}[i]}} f[j][1]\right)\]

State \(f[i][1]\) (peak): transitions from \(f[j][0]\), requiring \(\text{nums}[j] < \text{nums}[i]\), i.e., query the maximum \(f[\cdot][0]\) over the value range \([1,\ \text{nums}[i]-1]\):

\[f[i][1] = \text{nums}[i] + \max\!\left(0,\ \max_{\substack{j \leq i-k \\ \text{nums}[j] < \text{nums}[i]}} f[j][0]\right)\]

The final answer is \(\max_{0 \leq i < n}\max(f[i][0],\ f[i][1])\).

Optimization

The transitions involve dynamic prefix/suffix maximum queries over a value domain, which can be maintained efficiently with two Binary Indexed Trees (BITs):

BIT \(\text{bit}_0\): indexed by value, maintains the prefix maximum of \(f[\cdot][0]\), used to query cases where \(\text{nums}[j] < \text{nums}[i]\).
BIT \(\text{bit}_1\): indexed by \(m + 1 - \textit{rank}\) (reversed, where \(m\) is the number of distinct values), maintains the prefix maximum of \(f[\cdot][1]\), equivalent to a suffix maximum over the value domain, used to query cases where \(\text{nums}[j] > \text{nums}[i]\).

To ensure only indices \(j \leq i - k\) participate in transitions, when processing index \(i\), we first insert the state of index \(i - k\) into the BITs, then query.

The time complexity is \(O(n \log m)\) and the space complexity is \(O(n + m)\), where \(n\) is the length of the array and \(m\) is the number of distinct values.

Python3JavaC++Go

class BinaryIndexedTree:
    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, val: int) -> None:
        while x <= self.n:
            self.c[x] = max(self.c[x], val)
            x += x & -x

    def query(self, x: int) -> int:
        ans = 0
        while x > 0:
            ans = max(ans, self.c[x])
            x -= x & -x
        return ans


class Solution:
    def maxAlternatingSum(self, nums: List[int], k: int) -> int:
        vals = sorted(set(nums))
        m = len(vals)
        rank = {v: i + 1 for i, v in enumerate(vals)}
        bit0 = BinaryIndexedTree(m)
        bit1 = BinaryIndexedTree(m)
        n = len(nums)
        f = [[0, 0] for _ in range(n)]
        ans = 0
        for i, x in enumerate(nums):
            if i >= k:
                r = rank[nums[i - k]]
                bit0.update(r, f[i - k][0])
                bit1.update(m + 1 - r, f[i - k][1])
            r = rank[x]
            f[i][0] = x + bit1.query(m - r)
            f[i][1] = x + bit0.query(r - 1)
            ans = max(ans, f[i][0], f[i][1])
        return ans

class BinaryIndexedTree {
    private final int n;
    private final long[] c;

    BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new long[n + 1];
    }

    void update(int x, long val) {
        while (x <= n) {
            c[x] = Math.max(c[x], val);
            x += x & -x;
        }
    }

    long query(int x) {
        long ans = 0;
        while (x > 0) {
            ans = Math.max(ans, c[x]);
            x -= x & -x;
        }
        return ans;
    }
}

class Solution {
    public long maxAlternatingSum(int[] nums, int k) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int m = 0;
        for (int i = 0; i < sorted.length; ++i) {
            if (i == 0 || sorted[i] != sorted[i - 1]) {
                sorted[m++] = sorted[i];
            }
        }
        BinaryIndexedTree bit0 = new BinaryIndexedTree(m);
        BinaryIndexedTree bit1 = new BinaryIndexedTree(m);
        int n = nums.length;
        long[][] f = new long[n][2];
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= k) {
                int r = rank(sorted, m, nums[i - k]);
                bit0.update(r, f[i - k][0]);
                bit1.update(m + 1 - r, f[i - k][1]);
            }
            int r = rank(sorted, m, nums[i]);
            f[i][0] = nums[i] + bit1.query(m - r);
            f[i][1] = nums[i] + bit0.query(r - 1);
            ans = Math.max(ans, Math.max(f[i][0], f[i][1]));
        }
        return ans;
    }

    private int rank(int[] sorted, int m, int x) {
        int l = 0, r = m;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (sorted[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    }
}

class BinaryIndexedTree {
public:
    explicit BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1) {}

    void update(int x, long long val) {
        while (x <= n) {
            c[x] = max(c[x], val);
            x += x & -x;
        }
    }

    long long query(int x) {
        long long ans = 0;
        while (x > 0) {
            ans = max(ans, c[x]);
            x -= x & -x;
        }
        return ans;
    }

private:
    int n;
    vector<long long> c;
};

class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums, int k) {
        vector<int> sorted = nums;
        ranges::sort(sorted);
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        int m = sorted.size();
        auto rank = [&](int x) {
            return ranges::lower_bound(sorted, x) - sorted.begin() + 1;
        };
        BinaryIndexedTree bit0(m), bit1(m);
        int n = nums.size();
        vector<array<long long, 2>> f(n);
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= k) {
                int r = rank(nums[i - k]);
                bit0.update(r, f[i - k][0]);
                bit1.update(m + 1 - r, f[i - k][1]);
            }
            int r = rank(nums[i]);
            f[i][0] = nums[i] + bit1.query(m - r);
            f[i][1] = nums[i] + bit0.query(r - 1);
            ans = max({ans, f[i][0], f[i][1]});
        }
        return ans;
    }
};

type fenwick []int64

func (f fenwick) update(i int, val int64) {
    for ; i < len(f); i += i & -i {
        f[i] = max(f[i], val)
    }
}

func (f fenwick) query(i int) (res int64) {
    for ; i > 0; i &= i - 1 {
        res = max(res, f[i])
    }
    return
}

func maxAlternatingSum(nums []int, k int) (ans int64) {
    sorted := slices.Clone(nums)
    slices.Sort(sorted)
    sorted = slices.Compact(sorted)
    m := len(sorted)
    bit0 := make(fenwick, m+1)
    bit1 := make(fenwick, m+1)
    n := len(nums)
    f := make([][2]int64, n)
    for i, x := range nums {
        if i >= k {
            r := sort.SearchInts(sorted, nums[i-k]) + 1
            bit0.update(r, f[i-k][0])
            bit1.update(m+1-r, f[i-k][1])
        }
        r := sort.SearchInts(sorted, x) + 1
        f[i][0] = int64(x) + bit1.query(m-r)
        f[i][1] = int64(x) + bit0.query(r-1)
        ans = max(ans, f[i][0], f[i][1])
    }
    return
}

3915. Maximum Sum of Alternating Subsequence With Distance at Least K

Description

Solutions

Solution 1: Dynamic Programming + Binary Indexed Tree

Comments