3473. Sum of K Subarrays With Length at Least M LeetCode Solution
In this guide, you will get 3473. Sum of K Subarrays With Length at Least M LeetCode Solution with the best time and space complexity. The solution to Sum of K Subarrays With Length at Least M 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 Sum of K Subarrays With Length at Least M
You are given an integer array nums and two integers, k and m.
Return the maximum sum of k non-overlapping subarrays of nums, where each subarray has a length of at least m.
Example 1:
Input: nums = [1,2,-1,3,3,4], k = 2, m = 2
Output: 13
Explanation:
The optimal choice is:
Subarray nums[3..5] with sum 3 + 3 + 4 = 10 (length is 3 >= m).
Subarray nums[0..1] with sum 1 + 2 = 3 (length is 2 >= m).
The total sum is 10 + 3 = 13.
Example 2:
Input: nums = [-10,3,-1,-2], k = 4, m = 1
Output: -10
Explanation:
The optimal choice is choosing each element as a subarray. The output is (-10) + 3 + (-1) + (-2) = -10.
Constraints:
1 <= nums.length <= 2000
-104 <= nums[i] <= 104
1 <= k <= floor(nums.length / m)
1 <= m <= 3
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(nk)
3473. Sum of K Subarrays With Length at Least M LeetCode Solution in C++
class Solution {
public:
int maxSum(vector<int>& nums, int k, int m) {
const int n = nums.size();
vector<int> prefix(n + 1);
vector<vector<vector<int>>> mem(
n, vector<vector<int>>(2, vector<int>(k + 1, -1)));
partial_sum(nums.begin(), nums.end(), prefix.begin() + 1);
return maxSum(nums, 0, /*ongoing=*/0, k, m, prefix, mem);
}
private:
static constexpr int kInf = 20'000'000;
int maxSum(const vector<int>& nums, int i, int ongoing, int k, const int& m,
const vector<int>& prefix, vector<vector<vector<int>>>& mem) {
if (k < 0)
return -kInf;
if (i == nums.size())
return k == 0 ? 0 : -kInf;
if (mem[i][ongoing][k] != -1)
return mem[i][ongoing][k];
if (ongoing == 1)
// 1. End the current subarray (transition to state 0, same index i)
// 2. Extend the current subarray by picking nums[i] and move to i + 1.
return mem[i][1][k] =
max(maxSum(nums, i, 0, k, m, prefix, mem),
maxSum(nums, i + 1, 1, k, m, prefix, mem) + nums[i]);
// ongoing == 0
// 1. Skip nums[i].
// 2. Pick nums[i..i + m - 1] (only if k > 0 and there're enough elements).
int res = maxSum(nums, i + 1, 0, k, m, prefix, mem);
if (i + m <= nums.size()) // If we have enough elements for a new segment
res = max(res, maxSum(nums, i + m, 1, k - 1, m, prefix, mem) +
(prefix[i + m] - prefix[i]));
return mem[i][0][k] = res;
}
}; /* code provided by PROGIEZ */
3473. Sum of K Subarrays With Length at Least M LeetCode Solution in Java
class Solution {
public int maxSum(int[] nums, int k, int m) {
final int n = nums.length;
int[] prefix = new int[n + 1];
Integer[][][] mem = new Integer[n][2][k + 1];
for (int i = 0; i < n; i++)
prefix[i + 1] = prefix[i] + nums[i];
return maxSum(nums, 0, 0, k, m, prefix, mem);
}
private static final int INF = 20_000_000;
private int maxSum(int[] nums, int i, int ongoing, int k, int m, int[] prefix,
Integer[][][] mem) {
if (k < 0)
return -INF;
if (i == nums.length)
return k == 0 ? 0 : -INF;
if (mem[i][ongoing][k] != null)
return mem[i][ongoing][k];
if (ongoing == 1)
// 1. End the current subarray (transition to state 0, same index i)
// 2. Extend the current subarray by picking nums[i] and move to i + 1.
return mem[i][1][k] = Math.max(maxSum(nums, i, 0, k, m, prefix, mem),
maxSum(nums, i + 1, 1, k, m, prefix, mem) + nums[i]);
// ongoing == 0
// 1. Skip nums[i].
// 2. Pick nums[i..i + m - 1] (only if k > 0 and there're enough elements).
int res = maxSum(nums, i + 1, 0, k, m, prefix, mem);
if (i + m <= nums.length) // If we have enough elements for a new segment
res = Math.max(res,
maxSum(nums, i + m, 1, k - 1, m, prefix, mem) + (prefix[i + m] - prefix[i]));
return mem[i][0][k] = res;
}
} // code provided by PROGIEZ
3473. Sum of K Subarrays With Length at Least M LeetCode Solution in Python
class Solution:
def maxSum(self, nums: list[int], k: int, m: int) -> int:
INF = 20_000_000
n = len(nums)
prefix = list(itertools.accumulate(nums, initial=0))
@functools.lru_cache(None)
def dp(i: int, ongoing: int, k: int) -> int:
if k < 0:
return -INF
if i == n:
return 0 if k == 0 else -INF
if ongoing == 1:
# 1. End the current subarray (transition to state 0, same index i)
# 2. Extend the current subarray by picking nums[i] and move to i + 1
return max(dp(i, 0, k),
dp(i + 1, 1, k) + nums[i])
# ongoing == 0
# 1. Skip nums[i]
# 2. Pick nums[i:i+m] (only if k > 0 and there're enough elements)
res = dp(i + 1, 0, k)
if i + m <= n: # If we have enough elements for a new segment
res = max(res,
dp(i + m, 1, k - 1) + (prefix[i + m] - prefix[i]))
return res
return dp(0, 0, k) # code by PROGIEZ
