Practice Maximum Strength of K Disjoint Subarrays
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Choose exactly k nonempty, nonoverlapping subarrays of nums in left-to-right order, where k is odd. Gaps between chosen subarrays are allowed. The j-th chosen subarray has coefficient (k - j + 1), positive for odd j and negative for even j. Maximize the sum of each subarray sum multiplied by its coefficient. Practice approach: Use dynamic programming indexed by how many subarrays have been selected. Distinguish a state whose last subarray ends at the current element from a best-prefix state that may stop earlier. Either extend the current subarray or start it from the previous prefix's state for one fewer subarray. Impossible states must start at negative infinity, not zero, because exactly k nonempty subarrays are required. This supports O(nk) time and O(k) auxiliary space.
Source: Maximum Strength of K Disjoint Subarrays on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [1,2,3,-1,2], k = 3
22
The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and nums[4..4]. The strength is calculated as follows: strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22
# Example 2
nums = [12,-2,-2,-2,-2], k = 5
64
The only possible way to select 5 disjoint subarrays is: nums[0..0], nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is calculated as follows: strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64
# Example 3
nums = [-1,-2,-3], k = 1
-1
The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.
Constraints
Related LeetCode Problems
Practice more problems similar to Maximum Strength of K Disjoint Subarrays.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.