3691. Maximum Total Subarray Value II - Solution

The problem

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.

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.

Constraints:

1 <= n == nums.length <= 5 * 10⁴
0 <= nums[i] <= 10⁹
1 <= k <= min(10⁵, n * (n + 1) / 2)

Approach overview

Problem Overview: You are given an integer array and must compute the maximum possible total value obtained from subarrays according to the scoring rule defined in the problem. The challenge is efficiently identifying the best subarrays while avoiding overlapping or redundant calculations as the array size grows.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Enumerate every possible subarray using two nested loops for the start and end index. For each candidate range, compute its value by scanning the subarray and applying the scoring rule. This approach is useful for verifying correctness on small inputs but becomes impractical quickly because the number of subarrays is O(n²) and computing the value for each can take another O(n). Arrays larger than a few hundred elements will already be too slow.

Approach 2: Prefix Processing with Priority Queue (O(n^2 log n) time, O(n) space)

Precompute helper information such as prefix sums or other range statistics depending on the scoring formula. Instead of recalculating values repeatedly, maintain candidate subarrays and push them into a priority queue ordered by their potential contribution. Each step extracts the best candidate and expands or splits the range to generate new candidates. This reduces redundant computation but still explores many overlapping intervals. The heap improves selection of the next best subarray but the number of generated candidates can still reach O(n²).

Approach 3: Greedy Expansion with Segment Tree + Heap (O(n log n) time, O(n) space)

The optimal strategy treats each index or prefix boundary as a potential start of a high-value subarray. A segment tree stores range statistics (such as maximum prefix contribution or best extension point) so you can query the optimal end index for a given start in O(log n). Each candidate subarray is pushed into a heap (priority queue) ordered by its total value. When the best interval is chosen, the remaining search space is split into smaller intervals and reinserted as new candidates. This greedy best-first search avoids scanning the array repeatedly and guarantees that the highest-value segments are discovered first.

The key insight: instead of evaluating every subarray, treat the search space as ranges and always expand the currently best candidate. Efficient range queries from the array via the segment tree keep candidate generation fast while the heap ensures correct ordering.

Recommended for interviews: Start by explaining the brute force idea to show you understand the subarray search space. Then transition to the optimized greedy strategy using a heap and segment tree. Interviewers expect the O(n log n) solution because it demonstrates knowledge of advanced data structures and how to combine range queries with priority-based exploration.

Solution

Consider enumerating the left boundary l of the subarray. As the right boundary r moves to the right, the value of the subarray nums[l..r] increases monotonically. This is because the maximum value within the interval can only increase (or remain unchanged), while the minimum value can only decrease (or remain unchanged). Thus, their difference, max(nums[l..r]) - min(nums[l..r]), possesses a monotonically non-decreasing property.

This implies that for each fixed left endpoint l, we have a monotonically increasing sequence of length n - l, where the i-th element represents the value of nums[l..l+i]. The problem then transforms into: Given n monotonically increasing sequences, find the sum of the top k largest elements across all sequences.

Since the last element of each sequence (i.e., when r = n - 1) is the maximum value of that sequence, we can utilize a max-heap (priority queue) to filter them efficiently:

Initialization: Push the last element of each sequence (where r = n - 1) along with its coordinates, represented as (val, l, n - 1), into the max-heap.
Iterative Greedy Choice: Repeat the operation k times. In each iteration, pop the top element (val, l, r) from the heap and accumulate val into the total answer. If r > l, it indicates that there are still smaller, next-largest values remaining in this sequence. We then compute the value of the previous element in the same sequence, (l, r - 1), and push it back into the heap.
Range Minimum/Maximum Query Optimization: To query both the maximum and minimum values of any subarray [l, r] in \mathcal{O}(1) time, we can precompute a Sparse Table (ST).

The time complexity is \mathcal{O}(n log n + k log n), and the space Complexity is \mathcal{O}(n log n), where n is the length of the array nums.

Python

class SparseTableRMQ:
    def __init__(self, data: List[int]):
        self.n = len(data)
        self.max_log = self.n.bit_length() + 1
        self.f_max = [[0] * self.max_log for _ in range(self.n)]
        self.f_min = [[0] * self.max_log for _ in range(self.n)]

        self.lg = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.lg[i] = self.lg[i >> 1] + 1

        for i in range(self.n):
            self.f_max[i][0] = data[i]
            self.f_min[i][0] = data[i]

        for j in range(1, self.max_log):
            for i in range(self.n - (1 << j) + 1):
                self.f_max[i][j] = max(
                    self.f_max[i][j - 1], self.f_max[i + (1 << (j - 1))][j - 1]
                )
                self.f_min[i][j] = min(
                    self.f_min[i][j - 1], self.f_min[i + (1 << (j - 1))][j - 1]
                )

    def query_max(self, l: int, r: int) -> int:
        k = self.lg[r - l + 1]
        return max(self.f_max[l][k], self.f_max[r - (1 << k) + 1][k])

    def query_min(self, l: int, r: int) -> int:
        k = self.lg[r - l + 1]
        return min(self.f_min[l][k], self.f_min[r - (1 << k) + 1][k])


class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        st = SparseTableRMQ(nums)
        pq = []
        for l in range(n):
            val = st.query_max(l, n - 1) - st.query_min(l, n - 1)
            heappush(pq, (-val, l, n - 1))

        ans = 0
        for _ in range(k):
            val, l, r = heappop(pq)
            ans += -val
            if r > l:
                val = st.query_max(l, r - 1) - st.query_min(l, r - 1)
                heappush(pq, (-val, l, r - 1))
        return ans

Java

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

    public SparseTableRMQ(int[] data) {
        this.n = data.length;
        this.maxLog = 32 - Integer.numberOfLeadingZeros(n) + 1;
        this.fMax = new int[n][maxLog];
        this.fMin = new int[n][maxLog];
        this.lg = new int[n + 1];

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

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

        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i <= n - (1 << j); i++) {
                this.fMax[i][j]
                    = Math.max(this.fMax[i][j - 1], this.fMax[i + (1 << (j - 1))][j - 1]);
                this.fMin[i][j]
                    = Math.min(this.fMin[i][j - 1], this.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]);
    }
}

class Solution {
    public long maxTotalValue(int[] nums, int k) {
        int n = nums.length;
        SparseTableRMQ st = new SparseTableRMQ(nums);
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));

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

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

C++

class SparseTableRMQ {
public:
    int n;
    int maxLog;
    vector<vector<int>> fMax;
    vector<vector<int>> fMin;
    vector<int> lg;

    SparseTableRMQ(const vector<int>& data) {
        n = data.size();
        maxLog = 32 - __builtin_clz(n) + 1;
        fMax.assign(n, vector<int>(maxLog, 0));
        fMin.assign(n, vector<int>(maxLog, 0));
        lg.assign(n + 1, 0);

        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] = max(fMax[i][j - 1], fMax[i + (1 << (j - 1))][j - 1]);
                fMin[i][j] = min(fMin[i][j - 1], fMin[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

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

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

class Solution {
public:
    long long maxTotalValue(vector<int>& nums, int k) {
        int n = nums.size();
        SparseTableRMQ st(nums);
        auto cmp = [](const tuple<long long, int, int>& a, const tuple<long long, int, int>& b) {
            return get<0>(a) < get<0>(b);
        };
        priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, decltype(cmp)> pq(cmp);

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

        long long ans = 0;
        for (int i = 0; i < k; i++) {
            auto curr = pq.top();
            pq.pop();
            long long val = get<0>(curr);
            int l = get<1>(curr);
            int r = get<2>(curr);
            ans += val;
            if (r > l) {
                long long nextVal = st.queryMax(l, r - 1) - st.queryMin(l, r - 1);
                pq.push({nextVal, l, r - 1});
            }
        }
        return ans;
    }
};

TypeScript

class SparseTableRMQ {
    n: number;
    maxLog: number;
    fMax: number[][];
    fMin: number[][];
    lg: number[];

    constructor(data: number[]) {
        this.n = data.length;
        this.maxLog = Math.floor(Math.log2(this.n)) + 2;
        this.fMax = Array.from({ length: this.n }, () => Array(this.maxLog).fill(0));
        this.fMin = Array.from({ length: this.n }, () => Array(this.maxLog).fill(0));
        this.lg = Array(this.n + 1).fill(0);

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

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

        for (let j = 1; j < this.maxLog; j++) {
            for (let i = 0; i <= this.n - (1 << j); i++) {
                this.fMax[i][j] = Math.max(
                    this.fMax[i][j - 1],
                    this.fMax[i + (1 << (j - 1))][j - 1],
                );
                this.fMin[i][j] = Math.min(
                    this.fMin[i][j - 1],
                    this.fMin[i + (1 << (j - 1))][j - 1],
                );
            }
        }
    }

    queryMax(l: number, r: number): number {
        const k = this.lg[r - l + 1];
        return Math.max(this.fMax[l][k], this.fMax[r - (1 << k) + 1][k]);
    }

    queryMin(l: number, r: number): number {
        const k = this.lg[r - l + 1];
        return Math.min(this.fMin[l][k], this.fMin[r - (1 << k) + 1][k]);
    }
}

function maxTotalValue(nums: number[], k: number): number {
    const n = nums.length;
    const st = new SparseTableRMQ(nums);
    const pq = new PriorityQueue<[number, number, number]>((a, b) => b[0] - a[0]);

    for (let l = 0; l < n; l++) {
        const val = st.queryMax(l, n - 1) - st.queryMin(l, n - 1);
        pq.enqueue([val, l, n - 1]);
    }

    let ans = 0;
    for (let i = 0; i < k; i++) {
        if (pq.isEmpty()) break;
        const curr = pq.dequeue()!;
        const [val, l, r] = curr;
        ans += val;
        if (r > l) {
            const nextVal = st.queryMax(l, r - 1) - st.queryMin(l, r - 1);
            pq.enqueue([nextVal, l, r - 1]);
        }
    }
    return ans;
}

type SparseTableRMQ struct {
	n      int
	maxLog int
	fMax   [][]int
	fMin   [][]int
	lg     []int
}

func NewSparseTableRMQ(data []int) *SparseTableRMQ {
	n := len(data)
	maxLog := bits.Len(uint(n)) + 1
	fMax := make([][]int, n)
	fMin := make([][]int, n)
	for i := range fMax {
		fMax[i] = make([]int, maxLog)
		fMin[i] = make([]int, maxLog)
	}
	lg := make([]int, n+1)

	for i := 2; i <= n; i++ {
		lg[i] = lg[i>>1] + 1
	}

	for i := 0; i < n; i++ {
		fMax[i][0] = data[i]
		fMin[i][0] = data[i]
	}

	for j := 1; j < maxLog; j++ {
		for i := 0; i <= n-(1<<j); i++ {
			fMax[i][j] = max(fMax[i][j-1], fMax[i+(1<<(j-1))][j-1])
			fMin[i][j] = min(fMin[i][j-1], fMin[i+(1<<(j-1))][j-1])
		}
	}

	return &SparseTableRMQ{n: n, maxLog: maxLog, fMax: fMax, fMin: fMin, lg: lg}
}

func (st *SparseTableRMQ) queryMax(l, r int) int {
	k := st.lg[r-l+1]
	return max(st.fMax[l][k], st.fMax[r-(1<<k)+1][k])
}

func (st *SparseTableRMQ) queryMin(l, r int) int {
	k := st.lg[r-l+1]
	return min(st.fMin[l][k], st.fMin[r-(1<<k)+1][k])
}

type Item struct {
	val  int64
	l, r int
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].val > pq[j].val }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any)        { *pq = append(*pq, x.(*Item)) }
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func maxTotalValue(nums []int, k int) int64 {
	n := len(nums)
	st := NewSparseTableRMQ(nums)
	pq := &PriorityQueue{}
	heap.Init(pq)

	for l := 0; l < n; l++ {
		val := int64(st.queryMax(l, n-1) - st.queryMin(l, n-1))
		heap.Push(pq, &Item{val: val, l: l, r: n - 1})
	}

	var ans int64 = 0
	for i := 0; i < k; i++ {
		curr := heap.Pop(pq).(*Item)
		ans += curr.val
		if curr.r > curr.l {
			nextVal := int64(st.queryMax(curr.l, curr.r-1) - st.queryMin(curr.l, curr.r-1))
			heap.Push(pq, &Item{val: nextVal, l: curr.l, r: curr.r - 1})
		}
	}
	return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subarray Enumeration	O(n^3)	O(1)	Understanding the scoring rule or validating logic on very small arrays
Prefix Processing + Heap Candidates	O(n^2 log n)	O(n)	When partial range reuse helps but full optimization is not required
Greedy with Segment Tree + Priority Queue	O(n log n)	O(n)	General optimal solution for large arrays and interview settings

Frequently asked questions

Is Maximum Total Subarray Value II easy or hard?

Maximum Total Subarray Value II is considered a Hard problem with a low acceptance rate around 22%. The difficulty comes from combining greedy reasoning with advanced data structures like heaps and segment trees to achieve an O(n log n) solution.

Maximum Total Subarray Value II Python/Java solution

Python, Java, C++, and Go implementations typically follow the same pattern: build a segment tree for range queries, maintain a max heap of candidate intervals, and iteratively extract and split the best interval until all contributions are processed.

How to solve Maximum Total Subarray Value II in O(n log n)?

Preprocess the array to enable fast range evaluation, typically with prefix data and a segment tree. For each candidate start or interval, query the segment tree to find the best possible extension. Push candidates into a max heap ordered by subarray value and repeatedly expand the best interval while splitting remaining ranges.

What is the best approach for Maximum Total Subarray Value II?

The most efficient approach uses a greedy best-first search with a priority queue and a segment tree for fast range queries. Each candidate subarray is evaluated based on its potential value and stored in a heap. The segment tree helps find the optimal extension or boundary for a range in O(log n), resulting in an overall complexity of O(n log n).

Is Maximum Total Subarray Value II asked at Google/Amazon/Meta?

Hard array and range-query problems that combine greedy logic with segment trees or priority queues frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests the ability to combine multiple data structures for efficient range optimization.

What data structure is used in Maximum Total Subarray Value II?

The optimal solution relies on a segment tree for fast range queries and a priority queue (heap) for selecting the next highest-value candidate subarray. These structures work together to efficiently explore the best intervals in the array.

What is the time complexity of Maximum Total Subarray Value II?

The optimal solution runs in O(n log n) time and uses O(n) space. The log n factor comes from segment tree range queries and heap push/pop operations while processing candidate subarrays.

Maximum Total Subarray Value II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Maximum Total Subarray Value II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems