3077. Maximum Strength of K Disjoint Subarrays LeetCode Solution
In this guide, you will get 3077. Maximum Strength of K Disjoint Subarrays LeetCode Solution with the best time and space complexity. The solution to Maximum Strength of K Disjoint Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Strength of K Disjoint Subarrays
You are given an array of integers nums with length n, and a positive odd integer k.
Select exactly k disjoint subarrays sub1, sub2, …, subk from nums such that the last element of subi appears before the first element of sub{i+1} for all 1 <= i <= k-1. The goal is to maximize their combined strength.
The strength of the selected subarrays is defined as:
strength = k * sum(sub1)- (k – 1) * sum(sub2) + (k – 2) * sum(sub3) – … – 2 * sum(sub{k-1}) + sum(subk)
where sum(subi) is the sum of the elements in the i-th subarray.
Return the maximum possible strength that can be obtained from selecting exactly k disjoint subarrays from nums.
Note that the chosen subarrays don't need to cover the entire array.
Example 1:
Input: nums = [1,2,3,-1,2], k = 3
Output: 22
Explanation:
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:
Input: nums = [12,-2,-2,-2,-2], k = 5
Output: 64
Explanation:
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:
Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation:
The best possible way to select 1 subarray is: nums[0..0]. The strength is -1.
Constraints:
1 <= n <= 104
-109 <= nums[i] <= 109
1 <= k <= n
1 <= n * k <= 106
k is odd.
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(nk)
3077. Maximum Strength of K Disjoint Subarrays LeetCode Solution in C++
class Solution {
public:
long long maximumStrength(vector<int>& nums, int k) {
vector<vector<vector<long>>> mem(
nums.size(), vector<vector<long>>(k + 1, vector<long>(2, -1)));
return maximumStrength(nums, 0, k, /*fresh=*/true, mem);
}
private:
static constexpr long kMin = LONG_MIN / 2;
// Returns the maximum strength of nums[i..n) with k operations left, where
// `fresh` means we're starting a new subarray.
long maximumStrength(const vector<int>& nums, int i, int k, bool fresh,
vector<vector<vector<long>>>& mem) {
if (nums.size() - i < k)
return kMin;
if (k == 0)
return 0;
if (i == nums.size())
return k == 0 ? 0 : kMin;
if (mem[i][k][fresh] != -1)
return mem[i][k][fresh];
// If it's not fresh, we can't skip the current number and consider it as a
// fresh start, since the case where it's fresh is already covered by
// `includeAndFreshStart`.
const long skip = fresh ? maximumStrength(nums, i + 1, k, true, mem) : kMin;
const long gain = (k % 2 == 0 ? -1 : 1) * static_cast<long>(nums[i]) * k;
const long includeAndContinue =
maximumStrength(nums, i + 1, k, false, mem) + gain;
const long includeAndFreshStart =
maximumStrength(nums, i + 1, k - 1, true, mem) + gain;
return mem[i][k][fresh] =
max(skip, max(includeAndContinue, includeAndFreshStart));
}
}; /* code provided by PROGIEZ */
3077. Maximum Strength of K Disjoint Subarrays LeetCode Solution in Java
class Solution {
public long maximumStrength(int[] nums, int k) {
Long[][][] mem = new Long[nums.length][k + 1][2];
return maximumStrength(nums, 0, k, /*fresh=*/true, mem);
}
private static final long kMin = Long.MIN_VALUE / 2;
// Returns the maximum strength of nums[i..n) with k operations left, where
// `fresh` means we're starting a new subarray.
private long maximumStrength(int[] nums, int i, int k, boolean fresh, Long[][][] mem) {
if (nums.length - i < k)
return kMin;
if (k == 0)
return 0;
if (i == nums.length)
return k == 0 ? 0 : kMin;
if (mem[i][k][fresh ? 1 : 0] != null)
return mem[i][k][fresh ? 1 : 0];
// If it's not fresh, we can't skip the current number and consider it as a
// fresh start, since the case where it's fresh is already covered by
// `includeAndFreshStart`.
final long skip = fresh ? maximumStrength(nums, i + 1, k, true, mem) : kMin;
final long gain = (k % 2 == 0 ? -1 : 1) * 1L * nums[i] * k;
final long includeAndContinue = maximumStrength(nums, i + 1, k, false, mem) + gain;
final long includeAndFreshStart = maximumStrength(nums, i + 1, k - 1, true, mem) + gain;
return mem[i][k][fresh ? 1 : 0] =
Math.max(skip, Math.max(includeAndContinue, includeAndFreshStart));
}
} // code provided by PROGIEZ
3077. Maximum Strength of K Disjoint Subarrays LeetCode Solution in Python
class Solution:
def maximumStrength(self, nums: list[int], k: int) -> int:
@functools.lru_cache(None)
def dp(i: int, k: int, fresh: bool) -> int:
"""
Returns the maximum strength of nums[i..n) with k operations left, where
`fresh` means we're starting a new subarray.
"""
if len(nums) - i < k:
return -math.inf
if k == 0:
return 0
if i == len(nums):
return 0 if k == 0 else -math.inf
# If it's not fresh, we can't skip the current number and consider it as a
# fresh start, since the case where it's fresh is already covered by
# `includeAndFreshStart`.
skip = dp(i + 1, k, True) if fresh else -math.inf
gain = (-1 if k % 2 == 0 else 1) * nums[i] * k
includeAndContinue = dp(i + 1, k, False) + gain
includeAndFreshStart = dp(i + 1, k - 1, True) + gain
return max(skip, includeAndContinue, includeAndFreshStart)
return dp(0, k, True) # code by PROGIEZ
