Maximum Sum of 3 Non-Overlapping Subarrays

To solve this problem, we will first calculate the sum of each subarray of length k in the given array. Then we will use dynamic programming to find the maximum sum of three non-overlapping subarrays.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        sum_of_k = [0] * (n - k + 1)
        
        # Calculate the sum of subarrays of length k
        sum_of_k[0] = sum(nums[:k])
        for i in range(1, n - k + 1):
            sum_of_k[i] = sum_of_k[i - 1] + nums[i + k - 1] - nums[i - 1]

        # Left index represents the maximum sum from the left side for each window
        left = [0] * (n - k + 1)
        left_idx = 0
        for i in range(n - k + 1):
            if sum_of_k[i] > sum_of_k[left_idx]:
                left_idx = i
            left[i] = left_idx

        # Right index represents the maximum sum from the right side for each window
        right = [0] * (n - k + 1)
        right_idx = n - k
        for i in range(n - k, -1, -1):
            if sum_of_k[i] >= sum_of_k[right_idx]:
                right_idx = i
            right[i] = right_idx

        # Iterate through the middle window to find the maximum sum
        max_sum = 0
        result = []
        for j in range(k, n - 2 * k + 1):
            i, l = left[j - k], right[j + k]
            total = sum_of_k[i] + sum_of_k[j] + sum_of_k[l]
            if total > max_sum:
                max_sum = total
                result = [i, j, l]

        return result

The maxSumOfThreeSubarrays function first calculates the sum of each subarray of length k in nums. Then it uses dynamic programming to find the left and right maximum sums for each window and iterates through the middle window to find the maximum sum of three non-overlapping subarrays, returning the starting indices of those subarrays.

10 Prerequisite LeetCode Problems

“Maximum Sum of 3 Non-Overlapping Subarrays” requires a good understanding of arrays, dynamic programming, and sliding window concepts. Here are 10 problems to prepare for this problem:

1. “53. Maximum Subarray”: This problem will help you understand the Kadane’s algorithm which is fundamental for solving array related problems.

2. “209. Minimum Size Subarray Sum”: This problem introduces the sliding window concept, which is a crucial technique for solving this kind of problem.

3. “713. Subarray Product Less Than K”: This is a more complex problem using the sliding window concept.

4. “560. Subarray Sum Equals K”: This problem will help you get comfortable with handling subarrays and sums.

5. “325. Maximum Size Subarray Sum Equals k”: Similar to the previous problem but a bit more complex.

6. “152. Maximum Product Subarray”: This problem is a variant of the maximum subarray problem and will help you think about variations of subarray problems.

7. “238. Product of Array Except Self”: This problem requires careful handling of arrays and will help improve your skills in this area.

8. “628. Maximum Product of Three Numbers”: This problem will provide practice on finding maximum/minimum values within an array.

9. “376. Wiggle Subsequence”: This problem is another dynamic programming problem related to subarrays.

10. “918. Maximum Sum Circular Subarray”: This problem is a complex dynamic programming problem that will further deepen your understanding of the subject.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        memo = {}
        res = self.window_sum(nums, k, 0, 0, memo)
        return res[1]

    def window_sum(self, nums, k, idx, used, memo):
        if used == 3:
            return 0, []

        if idx - (used * k) > (len(nums)):
            return 0, []

        if (idx, used) in memo:
            return memo[(idx, used)]

        take_curr_sum, take_curr_indices = self.window_sum(nums, k, idx + k, used + 1, memo)
        take_curr_sum += sum(nums[idx:idx + k])

        skip_curr_sum, skip_curr_indices = self.window_sum(nums, k, idx + 1, used, memo)

        if take_curr_sum >= skip_curr_sum:
            memo[(idx, used)] = (take_curr_sum, ([idx] + take_curr_indices))
            return memo[(idx, used)]
        else:
            memo[(idx, used)] = (skip_curr_sum, skip_curr_indices)
            return memo[(idx, used)]

Problem Classification

This problem involves concepts of Arrays, Subarray and Optimization.

‘What’ components of the problem:

1. An array of integers, nums, is given. The length of nums is within the range from 1 to 2 * 104. Each integer in the array is within the range from 1 to 216 - 1.

2. An integer k is given. k is within the range from 1 to floor(nums.length / 3).

3. The task is to find three non-overlapping subarrays of length k from the array nums that have the maximum sum.

4. The output should be the starting indices of these three subarrays in nums. The indices are 0-indexed.

5. If multiple answers are possible, the output should be the lexicographically smallest one.

We can further classify this problem as a Search Problem, since it involves finding specific subarrays in the given array, and an Optimization Problem, as we need to find the subarrays with maximum sums. It is also a Combinatorial Problem because we need to evaluate combinations of subarrays, and a Greedy Problem since we need to find the lexicographically smallest answer among multiple possible answers.

The problem statement can be classified in the following manner:

1. Array Manipulation: The problem involves performing operations on an array of integers.

2. Optimization Problem: The goal is to find the three non-overlapping subarrays with maximum sum, which is an optimization task.

3. Subarray Problem: We’re looking for specific subarrays in an array which fulfill certain conditions.

4. Dynamic Programming: This problem requires considering all possible combinations of subarrays to achieve the solution. It employs principles of dynamic programming, as it needs to solve overlapping subproblems and combines their solutions to build the final answer.

5. Memoization: The problem involves using memoization to avoid recomputation of subproblems. This is a key feature of many dynamic programming problems.

6. Sliding Window: As the problem focuses on finding subarrays of a specific length, it is a sliding window problem as well.

Note that while these categories do not directly tell you the specific algorithm or technique to use, they do provide a good starting point for tackling the problem and identify the techniques that are likely to be useful.

Language Agnostic Coding Drills

1. Dissecting the code:

Here are the distinct concepts it contains:

• Basic Programming Constructs: This includes the definition of variables, arrays, and classes, loops (both for and while), conditional statements (if-else), function definition and invocation.

• Array Manipulation: This involves creating and updating arrays, accessing array elements by index.

• Prefix Sum Computation: This involves creating a new array where each element is the sum of all elements before it in the original array.

• Dynamic Programming: This includes creating and updating arrays based on previously computed values. In this case, dynamic programming is used to maintain the positions of maximum sum subarrays.

• Iteration over Array in Reverse Order: This involves iterating over the elements of an array in reverse order.

• Optimization techniques: This involves keeping track of the maximum value encountered during iteration over an array and updating it when a larger value is found.

2. Increasing order of difficulty:

• Basic Programming Constructs: This is the most fundamental level and is the first thing one would learn in any programming language. It’s the building block of any code.

• Array Manipulation: While still a basic concept, it requires understanding of how to access and manipulate data in a structured way, which could be a bit more challenging for beginners.

• Prefix Sum Computation: This is a step up in difficulty as it requires understanding of both arrays and loops, and the ability to perform computations on array elements based on their positions.

• Iteration over Array in Reverse Order: This involves more complex loop manipulation and can be tricky to get right.

• Dynamic Programming: This is more advanced as it involves breaking down a problem into subproblems and solving them in an optimal way. It requires good problem-solving skills and a deep understanding of programming constructs.

• Optimization techniques: This is the most advanced concept as it involves developing efficient solutions. It requires a good understanding of algorithms and data structures, and the ability to reason about the efficiency of code.

3. Problem-solving approach:

• Understand the Problem: The first step in solving any problem is understanding the problem statement and requirements thoroughly.

• Identify Sub-Problems: Based on the problem requirements, identify the sub-problems that need to be solved. In this case, the sub-problems are finding three non-overlapping subarrays of maximum sum.

• Implement Basic Constructs: Begin by defining the necessary variables, arrays and function.

• Compute Prefix Sum: Calculate the prefix sum of the array, which will be used to efficiently calculate the sum of subarrays.

• Dynamic Programming for Left and Right Max Sum: Use dynamic programming to keep track of the position of the maximum sum subarray ending at each position from the left and starting at each position from the right.

• Iterate Over Possible Middle Intervals: Loop over all possible positions for the middle subarray, calculate the total sum for each configuration of three subarrays, and keep track of the maximum sum encountered.

• Return Result: Finally, return the positions of the subarrays that produce the maximum sum. This is the final result of the function.

This problem involves the usage of “Dynamic Programming”, “Sliding Window”, and “Memoization”. The solution approach involves maximizing the sum of three subarrays of length ‘k’. Here are the small learning units that make up the solution:

1. Understanding Dynamic Programming (DP): DP is a method for solving complex problems by breaking them down into simpler subproblems. It is used when the subproblems are not independent, i.e., the solution to one subproblem may involve solutions of other subproblems. The key idea is to save the results of subproblems so they do not have to be recomputed, which is known as “memoization”.

2. Understanding Sliding Window technique: This is an algorithmic paradigm that manages and checks the condition of a subset of data points from a set of larger data points given a condition, a.k.a. the window. For this problem, the window size is ‘k’.

3. Understand Recursive Function Calls: Recursive functions are functions that call themselves to solve a smaller instance of the original problem. The function should have a base case to terminate the recursion.

4. Subarray sums: Calculating the sum of elements in a subarray is a key part of this problem.

5. Understand Memoization: This is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and reusing them when the same inputs occur again.

Given these concepts, here’s a step-by-step approach to solving the problem:

1. The problem is solved using a recursive function window_sum that calculates the maximum sum of subarrays that can be obtained from index idx onwards, using exactly used subarrays. The function returns a tuple with the maximum sum and the indices of the subarrays that lead to the maximum sum.

2. Two choices are available at every call of the function: either take the subarray starting at index idx (of size k) or skip it. Recursive calls are made for both choices. The sum of the subarray is added to the result of the recursive call in the case of taking the subarray.

3. The function uses memoization to avoid repeated calculation for the same state (represented by idx and used). If a state has been computed before, the function returns the stored result. If not, it computes the result, stores it, and then returns it.

4. After the recursive process, the function checks which choice (taking or skipping the subarray) gives the maximum sum and returns the corresponding result.

5. The main function maxSumOfThreeSubarrays initializes the memoization dictionary and calls the window_sum function. It then returns the indices of the subarrays leading to the maximum sum.

6. The base case for the recursion is when 3 subarrays have been used (used == 3), in which case the function returns a sum of 0 and an empty list of indices. If the remaining part of the array is shorter than the required number of subarrays of size k, the function also returns a sum of 0 and an empty list of indices.

Targeted Drills in Python

Sure, let’s write some practice drills to learn the individual concepts used in the solution.

1. Understanding Dynamic Programming (DP):

   • Problem: Write a function that calculates the n-th Fibonacci number using dynamic programming.

   1 2 3 4 5

   def fibonacci(n): fib = [0, 1] + [0]*(n-1) for i in range(2, n+1): fib[i] = fib[i-1] + fib[i-2] return fib[n]

2. Understanding Sliding Window Technique:

   • Problem: Given an array, find the maximum (or minimum) sum of a subarray of a specified size.

   1 2 3 4 5 6 7

   def max_subarray_sum(nums, k): curr_sum = sum(nums[:k]) max_sum = curr_sum for i in range(k, len(nums)): curr_sum = curr_sum - nums[i - k] + nums[i] max_sum = max(max_sum, curr_sum) return max_sum

3. Understand Recursive Function Calls:

   • Problem: Write a function to calculate factorial of a number using recursion.

   1 2 3 4 5

   def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n - 1)

4. Subarray sums:

   • Problem: Write a function to calculate the sum of a subarray given the starting and ending index.

   1 2	def subarray_sum(nums, start, end): return sum(nums[start:end+1])

5. Understand Memoization:

   • Problem: Write a recursive function to calculate the n-th Fibonacci number using memoization.

   1 2 3 4 5 6 7 8

   def fibonacci_memo(n, memo = {}): if n in memo: return memo[n] elif n <= 2: return 1 else: memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo) return memo[n]

The final problem is a complex one that combines all these drills together into one. It’s important to understand each of these concepts well before trying to understand the final solution.