题目

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

思路

线段树

解法

class Solution {
public int constrainedSubsetSum(int[] nums, int k) {
    int n = nums.length;
    t = new int[n << 2];
    for (int i = 0; i < n; i++) {
        int val = nums[i];
        int q = query(1, 0, n - 1, i - k, i);
        val = Math.max(val, val + q);
        update(1, 0, n - 1, i, val);

    }
    return query(1, 0, n - 1, 0, n - 1);
}

private int[] t;

private void update(int rt, int l, int r, int i, int val) {
    if (l == r) {
        t[rt] = val;
        return;
    }
    int m = (l + r) >> 1;
    if (i <= m) {
        update(rt << 1, l, m, i, val);
    } else {
        update(rt << 1 | 1, m + 1, r, i, val);
    }
    maintain(rt);
}

private int query(int rt, int l, int r, int L, int R) {

    if (L <= l && r <= R) {
        return t[rt];
    }

    int m = (l + r) >> 1;
    int res = Integer.MIN_VALUE;
    if (L <= m) {
        res = Math.max(res, query(rt << 1, l, m, L, R));
    }
    if (m < R) {
        res = Math.max(res, query(rt << 1 | 1, m + 1, r, L, R));
    }

    return res;
}

private void maintain(int rt) {
    t[rt] = Math.max(t[rt << 1], t[rt << 1 | 1]);
}
}

总结

• 分析出几种情况，然后分别对各个情况实现