3691. Maximum Total Subarray Value II

Intuition

For a fixed left endpoint l, the subarray value max(nums[l..r]) - min(nums[l..r]) is largest when r is farthest to the right, and it never increases when we shrink r leftward. That means every left endpoint produces a sorted stream of candidate values. A max-heap can merge these n streams: always take the current best subarray, then reveal the next smaller candidate from the same left endpoint.

Algorithm

1Build a sparse table that can answer range maximum and range minimum queries in O(1).
2For every left endpoint l, compute value(l, n-1) and push [value, l, n-1] into a max-heap.
3Repeat up to k times while the heap is non-empty.
4Pop the largest available candidate and add its value to the answer.
5If its right endpoint r is still greater than l, compute value(l, r-1) and push that next candidate for the same left endpoint.
6Return the accumulated answer as a long.
7Time Complexity: O(n log n + (n + k) log n): sparse-table preprocessing plus heap initialization and k heap pops/pushes.
8Space Complexity: O(n log n), dominated by the sparse tables for range max/min.

Example Walkthrough

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

1.For l = 0, candidates by shrinking r are [1,3,2] -> 2, [1,3] -> 2, [1] -> 0.
2.For l = 1, candidates are [3,2] -> 1, [3] -> 0.
3.For l = 2, candidate is [2] -> 0.
4.The heap first contains values 2, 1, and 0. Pop 2 from l=0, then push the next l=0 value 2.
5.Pop 2 again, then pop 1. The top 3 total is 2 + 2 + 1 = 5.

Output: 5

Common Pitfalls

•Do not recompute max and min by scanning every subarray; that becomes too slow.
•The heap entry must carry both l and r so the next candidate for the same left endpoint can be generated correctly.
•Use long for the answer because the sum of k selected values can exceed int range.

3691.cs

// Approach: Build a sparse table for O(1) range max/min queries. For each left endpoint,
// push the value of its longest suffix subarray into a max-heap; whenever that candidate is
// chosen, shrink its right endpoint by one and push the next candidate for the same left.
// Time: O(n log n + (n + k) log n) Space: O(n log n)

class SparseTableRMQ
{
    int n;
    int maxLog;
    int[][] fMax;
    int[][] fMin;
    int[] lg;

    public SparseTableRMQ(int[] data)
    {
        n = data.Length;
        maxLog = 32 - CountLeadingZeros(n) + 1;
        fMax = new int[n][];
        fMin = new int[n][];
        for (int i = 0; i < n; i++)
        {
            fMax[i] = new int[maxLog];
            fMin[i] = new int[maxLog];
        }
        lg = new int[n + 1];

        for (int i = 2; i <= n; i++)
        {
            lg[i] = lg[i >> 1] + 1;
        }

        for (int i = 0; i < n; i++)
        {
            fMax[i][0] = data[i];
            fMin[i][0] = data[i];
        }

        for (int j = 1; j < maxLog; j++)
        {
            for (int i = 0; i <= n - (1 << j); i++)
            {
                fMax[i][j] = Math.Max(fMax[i][j - 1], fMax[i + (1 << (j - 1))][j - 1]);
                fMin[i][j] = Math.Min(fMin[i][j - 1], fMin[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    public int queryMax(int l, int r)
    {
        int k = lg[r - l + 1];
        return Math.Max(fMax[l][k], fMax[r - (1 << k) + 1][k]);
    }

    public int queryMin(int l, int r)
    {
        int k = lg[r - l + 1];
        return Math.Min(fMin[l][k], fMin[r - (1 << k) + 1][k]);
    }

    private static int CountLeadingZeros(int x)
    {
        // Count leading zeros for 32-bit integer
        if (x == 0) return 32;
        int n = 0;
        if ((x & 0xFFFF0000) == 0) { n += 16; x <<= 16; }
        if ((x & 0xFF000000) == 0) { n += 8; x <<= 8; }
        if ((x & 0xF0000000) == 0) { n += 4; x <<= 4; }
        if ((x & 0xC0000000) == 0) { n += 2; x <<= 2; }
        if ((x & 0x80000000) == 0) { n += 1; }
        return n;
    }
}

class Solution
{
    public long MaxTotalValue(int[] nums, int k)
    {
        int n = nums.Length;
        SparseTableRMQ st = new SparseTableRMQ(nums);
        var pq = new PriorityQueue<long[], long>(Comparer<long>.Create((a, b) => b.CompareTo(a)));

        for (int l = 0; l < n; l++)
        {
            long val = (long)st.queryMax(l, n - 1) - st.queryMin(l, n - 1);
            pq.Enqueue(new long[] { val, l, n - 1 }, val);
        }

        long ans = 0;
        for (int i = 0; i < k && pq.Count > 0; i++)
        {
            var curr = pq.Dequeue();
            long val = curr[0];
            int l = (int)curr[1];
            int r = (int)curr[2];
            ans += val;
            if (r > l)
            {
                long nextVal = (long)st.queryMax(l, r - 1) - st.queryMin(l, r - 1);
                pq.Enqueue(new long[] { nextVal, l, r - 1 }, nextVal);
            }
        }
        return ans;
    }
}

Was this solution helpful?