LeetCode in Kotlin

3957. Maximum Sum of M Non-Overlapping Subarrays II

Hard

You are given an integer array nums of length n, and three integers m, l, and r.

Your task is to select at least one and at most m non-overlapping non-empty subarrays from nums such that:

• Each selected subarray has a length between [l, r] (inclusive).
• The total sum of all selected subarrays is maximized.

Return the maximum total sum you can achieve.

Example 1:

Input: nums = [4,1,-5,2], m = 2, l = 1, r = 3

Output: 7

Explanation:

One optimal strategy is to:

• Select the subarray [4, 1] with sum 4 + 1 = 5 and the subarray [2] with sum 2. Both subarrays have length between [l, r].
• The total sum of these subarrays is 5 + 2 = 7, which is the maximum achievable sum with at most m = 2 subarrays.

Example 2:

Input: nums = [1,0,3,4], m = 2, l = 1, r = 2

Output: 8

Explanation:

One optimal strategy is to:

• Select the subarray [1] with sum 1 and the subarray [3, 4] with sum 3 + 4 = 7. Both subarrays have length between [l, r].
• The total sum of these subarrays is 1 + 7 = 8, which is the maximum achievable sum with at most m = 2 subarrays.

Example 3:

Input: nums = [-1,7,-4], m = 1, l = 2, r = 3

Output: 6

Explanation:

• Select the subarray [-1, 7] from nums which has length between [l, r].
• The total sum of this subarray is -1 + 7 = 6, which is the maximum achievable sum with at most m = 1 subarray.

Example 4:

Input: nums = [-3,-4,-1], m = 2, l = 1, r = 2

Output: -1

Explanation:

• All subarrays of nums have negative sums. The optimal strategy is to select the subarray [-1], which has length between [l, r].
• The total sum of this subarray is -1, which is the maximum achievable sum with at most m = 2 subarrays.

Constraints:

• 1 <= n == nums.length <= 105
• -105 <= nums[i] <= 105
• 1 <= m <= n
• 1 <= l <= r <= n

Solution

class Solution {
    private lateinit var pre: LongArray
    private lateinit var `val`: LongArray
    private lateinit var cnt: IntArray
    private lateinit var dq: IntArray
    private var n = 0
    private var l = 0
    private var r = 0

    fun maximumSum(nums: IntArray, m: Int, l: Int, r: Int): Long {
        n = nums.size
        this.l = l
        this.r = r
        pre = LongArray(n + 1)
        for (i in 0..<n) {
            pre[i + 1] = pre[i] + nums[i]
        }
        `val` = LongArray(n + 1)
        cnt = IntArray(n + 1)
        dq = IntArray(n + 2)
        var lo: Long = 0
        var hi = 20000000000L
        var ansLambda = hi
        solve(0)
        if (cnt[n] <= m) {
            return `val`[n]
        }
        while (lo <= hi) {
            val mid = lo + (hi - lo) / 2
            solve(mid)
            if (cnt[n] <= m) {
                ansLambda = mid
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        }
        solve(ansLambda)
        return `val`[n] + ansLambda * m
    }

    private fun solve(lambda: Long) {
        val neg = Long.MIN_VALUE / 4
        `val`[0] = neg
        cnt[0] = 0
        var head = 0
        var tail = 0
        for (i in 1..n) {
            val j = i - l
            if (j >= 0) {
                tail = addCandidate(j, head, tail)
            }
            head = removeExpiredCandidates(head, tail, i - r)
            var bestV = `val`[i - 1]
            var bestC = cnt[i - 1]
            if (tail > head) {
                val b = dq[head]
                val cand = normalizedValue(b) - pre[b] + pre[i] - lambda
                val candC = normalizedCount(b) + 1
                if (isBetter(cand, candC, bestV, bestC)) {
                    bestV = cand
                    bestC = candC
                }
            }
            `val`[i] = bestV
            cnt[i] = bestC
        }
    }

    private fun addCandidate(j: Int, head: Int, tail: Int): Int {
        var tail = tail
        val key = normalizedValue(j) - pre[j]
        val candidateCount = normalizedCount(j)
        while (tail > head) {
            val t = dq[tail - 1]
            val tailKey = normalizedValue(t) - pre[t]
            val tailCount = normalizedCount(t)
            if (tailKey < key || (tailKey == key && tailCount >= candidateCount)) {
                tail--
            } else {
                break
            }
        }
        dq[tail++] = j
        return tail
    }

    private fun removeExpiredCandidates(head: Int, tail: Int, minIndex: Int): Int {
        var head = head
        while (tail > head && dq[head] < minIndex) {
            head++
        }
        return head
    }

    private fun normalizedValue(index: Int): Long = if (`val`[index] > 0) `val`[index] else 0

    private fun normalizedCount(index: Int): Int = if (`val`[index] > 0) cnt[index] else 0

    private fun isBetter(candidateValue: Long, candidateCount: Int, bestValue: Long, bestCount: Int): Boolean =
        candidateValue > bestValue ||
            (candidateValue == bestValue && candidateCount < bestCount)
}

This site is open source. Improve this page.