LeetCode Ts-3691. Maximum Total Subarray Value II

You are given an integer array nums of length n and an integer k.
You must select exactly k distinct non-empty subarrays nums[l..r] of nums. Subarrays may overlap, but the exact same subarray (same l and r) cannot be chosen more than once.
The value of a subarray nums[l..r] is defined as: max(nums[l..r]) – min(nums[l..r]).
The total value is the sum of the values of all chosen subarrays.
Return the maximum possible total value you can achieve.

你給予一個整數陣列 nums（長度為 n）和一個整數 k。
你需要選擇恰好 k 個不同的非空子陣列，子陣列可以重疊，但不能選擇完全相同（相同的 l 和 r）的子陣列超過一次。
每個子陣列的定義為：max(nums[l..r]) - min(nums[l..r])
total value 是所有選中子陣列的值總和。
回傳能夠得到的最大 total value。

Example 1:

Input: nums = [1,3,2], k = 2
Output: 4
Explanation:
One optimal approach is:
Choose nums[0..1] = [1, 3]. The maximum is 3 and the minimum is 1, giving a value of 3 - 1 = 2.
Choose nums[0..2] = [1, 3, 2]. The maximum is still 3 and the minimum is still 1, so the value is also 3 - 1 = 2.
Adding these gives 2 + 2 = 4.

Example 2:

Input: nums = [4,2,5,1], k = 3
Output: 12
Explanation:
One optimal approach is:
Choose nums[0..3] = [4, 2, 5, 1]. The maximum is 5 and the minimum is 1, giving a value of 5 - 1 = 4.
Choose nums[1..3] = [2, 5, 1]. The maximum is 5 and the minimum is 1, so the value is also 4.
Choose nums[2..3] = [5, 1]. The maximum is 5 and the minimum is 1, so the value is again 4.
Adding these gives 4 + 4 + 4 = 12.

Solution:
題目要求選取 k 個不重疊的子陣列，並最大化 (max – min) 的總和。
為了能快速查詢任意子區間的最小值與最大值，我們使用 Segment Tree (BigO(log n))。
– 建立 Node，存放 [a,b] 區間以及 minVal、maxVal。
– 建立 Segment，用來存放子區間 [l,r] 及其差值。
– 使用 MaxHeap，每次取出目前差值最大的子區間。
– 當取出 [l,r] 後，將它「切割」成 [l,r-1] 與 [l+1,r]，避免重疊與持續查找更多子區間。
– 用 Set 紀錄已使用的區間，避免重複推入。
– 重複取 k 次，累加答案並輸出。

Code 1: BigO(n + k log n)

class Node {
    l: Node | null = null;
    r: Node | null = null;
    a: number;
    b: number;
    maxVal: number = 0;
    minVal: number = 0;
    constructor(a: number, b: number) {
        this.a = a;
        this.b = b;
    }
}

class Segment {
    l: number;
    r: number;
    val: number;
    constructor(l: number, r: number, val: number) {
        this.l = l;
        this.r = r;
        this.val = val;
    }
}

class CustomizeMaxHeap {
    data: Segment[] = [];
    size() { return this.data.length; }
    push(seg: Segment) {
        this.data.push(seg);
        this._siftUp(this.data.length - 1);
    }
    pop(): Segment | undefined {
        if (this.data.length === 0) return undefined;
        const top = this.data[0];
        const last = this.data.pop()!;
        if (this.data.length > 0) {
            this.data[0] = last;
            this._siftDown(0);
        }
        return top;
    }
    private _siftUp(i: number) {
        while (i > 0) {
            const p = Math.floor((i - 1) / 2);
            if (this.data[i].val > this.data[p].val) {
                [this.data[i], this.data[p]] = [this.data[p], this.data[i]];
                i = p;
            } else break;
        }
    }
    private _siftDown(i: number) {
        const n = this.data.length;
        while (true) {
            let largest = i;
            const l = i * 2 + 1, r = i * 2 + 2;
            if (l < n && this.data[l].val > this.data[largest].val) largest = l;
            if (r < n && this.data[r].val > this.data[largest].val) largest = r;
            if (largest !== i) {
                [this.data[i], this.data[largest]] = [this.data[largest], this.data[i]];
                i = largest;
            } else break;
        }
    }
}

function buildSegmentTree(nums: number[], a: number, b: number): Node {
    const node = new Node(a, b);
    if (a === b) {
        node.minVal = node.maxVal = nums[a];
        return node;
    }
    const mid = Math.floor((a + b) / 2);
    node.l = buildSegmentTree(nums, a, mid);
    node.r = buildSegmentTree(nums, mid + 1, b);
    node.minVal = Math.min(node.l.minVal, node.r.minVal);
    node.maxVal = Math.max(node.l.maxVal, node.r.maxVal);
    return node;
}

function querySegmentTree(node: Node, l: number, r: number): [number, number] {
    if (node.a >= l && node.b <= r) return [node.minVal, node.maxVal];
    if (node.b < l || node.a > r) return [1e9, -1e9];
    const [minL, maxL] = querySegmentTree(node.l!, l, r);
    const [minR, maxR] = querySegmentTree(node.r!, l, r);
    return [Math.min(minL, minR), Math.max(maxL, maxR)];
}

function makeKey(l: number, r: number) { return `${l},${r}`; }

function maxTotalValue(nums: number[], k: number): number {
    const n = nums.length;
    const root = buildSegmentTree(nums, 0, n - 1);
    const used = new Set();
    const heap = new CustomizeMaxHeap();

    const [minWhole, maxWhole] = querySegmentTree(root, 0, n - 1);
    heap.push(new Segment(0, n - 1, maxWhole - minWhole));
    used.add(makeKey(0, n - 1));

    let ans = 0;

    while (k-- > 0 && heap.size() > 0) {
        const segment = heap.pop()!;
        ans += segment.val;
        const { l, r } = segment;

        if (l < r) {            
            const leftKey = makeKey(l, r - 1);
            if (!used.has(leftKey)) {
                const [minL, maxL] = querySegmentTree(root, l, r - 1);
                heap.push(new Segment(l, r - 1, maxL - minL));
                used.add(leftKey);
            }        
            const rightKey = makeKey(l + 1, r);
            if (!used.has(rightKey)) {
                const [minR, maxR] = querySegmentTree(root, l + 1, r);
                heap.push(new Segment(l + 1, r, maxR - minR));
                used.add(rightKey);
            }
        }
    }
    return ans;
}

FlowChart:
Example 1

heap CustomizeMaxHeap { data: [ Segment { l: 0, r: 2, val: 2 } ] }
used Set(1) { '0,2' }

Choose nums[0..2] = [1,3,2], value=2, ans=2
segment Segment { l: 0, r: 2, val: 2 } ans 2

Choose nums[0..1] = [1,3], value=2, ans=4
segment Segment { l: 0, r: 1, val: 2 } ans 4