1043. Partition Array for Maximum Sum

MediumArrayDynamic Programming
Leetcode Link

Problem Description

The problem presents us with an integer array arr and asks us to partition this array into continuous subarrays. Each of these subarrays can have a length of up to k, which is given as part of the input. After partitioning the array into these subarrays, we need to modify each subarray so that all its elements are equal to the maximum value in that subarray.

Our goal is to find the largest possible sum that can be obtained from the array after completing this partition and modification process. It's important to note that when choosing how to partition the array, we're looking for the method that will lead to this maximum sum. We are assured that the answer will not exceed the capacity of a 32-bit integer.

The intuitive challenge is to balance between creating subarrays with high maximum values and making these subarrays as large as possible, since the final sum will be influenced by both the size of the subarrays and the value to which their elements are set.

Intuition

The solution to this problem employs a dynamic programming approach, which is a method used to solve complex problems by breaking them down into simpler subproblems. The key insight in dynamic programming is that the solution to the overall problem depends on the solutions to its subproblems, and these subproblems often overlap.

In this case, our subproblems involve determining the maximum sum that can be obtained from the first i elements of the array for each i from 1 to n, where n is the total number of elements in arr.

We start by defining f[i] as the maximum sum obtainable from the first i elements after partitioning. To compute f[i], we need to consider all possible ends for the last subarray that ends at position i. This involves looking at each possible starting position j for this subarray that is not more than k indices before i. As we consider each possible j, we keep track of the maximum value mx within this range and update f[i] by considering the maximum sum that can be achieved by making arr[j - 1] the first element of the last subarray.

The transition equation helps us update f[i] by considering the value of f[i] before adding the new subarray and the additional sum that comes from setting all elements in the current subarray to the maximum value found (mx multiplied by the length of the subarray, which is (i - j + 1)).

By iteratively building up from smaller subarrays to the full array, we ensure that each f[i] contains the optimum solution for the first i elements, and hence f[n] gives us the answer for the entire array.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Solution Approach

The problem is approached using a dynamic programming technique. Here is a step-by-step explanation of how the solution is implemented, corresponding to the provided Python code:

  1. Dynamic Programming Array Initialization:

    • A dynamic programming array f is initialized with a length of n + 1, where f[i] will eventually store the maximum sum obtainable for the first i elements of arr.
    • This array is initially filled with zeroes, as we have not yet computed any subarray sums.

  2. Nested Loop Structure:

    • We iterate through the array using a variable i which goes from 1 to n, inclusive. This represents the rightmost element of the current subarray window we are considering.
    • Within this outer loop, we have an inner reverse loop with a variable j that starts from i and goes backwards to max(0, i - k), considering each possible subarray that ends at position i and has a length of at most k.

  3. Maximum Subarray Value:

    • A variable mx is used to keep track of the maximum value in the subarray starting from a potential starting point j.
    • As we move leftwards in the inner loop (j decreases), we update mx to reflect the maximum value encountered so far using the expression mx = max(mx, arr[j - 1]).

  4. Updating Dynamic Programming Array:

    • We then calculate the sum of the current subarray by multiplying the largest number found (mx) by the size of the subarray (which is (i - j + 1)). This reflects the sum of the partitioned subarray if all of its values are changed to the maximum value found in it.

    • The dynamic programming array f[i] is updated with the maximum of its current value and the sum of the subarray formed by adding the newly computed subarray sum to the maximum sum achievable before the current subarray (f[j - 1]).

    • The state transition equation used here is:

      1f[i] = max(f[i], f[j - 1] + mx * (i - j + 1))

  5. Return the Final Answer:

    • After populating the dynamic programming array with the best solutions for all subarray sizes, the final answer to the problem is the last element of the array, f[n], which represents the maximum sum obtainable for the entire array.

By using dynamic programming, the solution avoids recomputing the sums for overlapping subproblems, which makes it efficient. The space complexity of the algorithm is linear (O(n)) due to the use of the dynamic programming array, and the time complexity is O(n * k) because of the nested loops, where for each i, a maximum of k positions is considered.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's consider arr = [1, 15, 7, 9, 2, 5, 10] with k = 3. Our task is to partition arr into continuous subarrays of length at most k, and then maximize the sum of the array after each element in a subarray has been made equal to the maximum element of that subarray.

  1. We start with f[0] = 0 because no elements give a sum of 0.

  2. For i = 1 (arr[0] = 1), the only subarray we can have is [1], and the maximum sum we can obtain is 1*(1) = 1. So, f[1] = 1.

  3. At i = 2 (arr[1] = 15), we could have a subarray [1, 15] or just [15]. The best option is to make subarray [15] because 15*(1) = 15 is greater than 15*(2) - 1*(1) = 29. So, f[2] = 15.

  4. Moving on to i = 3 (arr[2] = 7), we could have [1, 15, 7], [15, 7], or just [7]. The choice [15, 7] gives us the highest sum because 15*(2) = 30, while the others give lower sums. Adding the previous f[1], we get f[3] = f[1] + 15*2 = 1 + 30 = 31.

  5. For i = 4 (arr[3] = 9), the potential subarrays are [1, 15, 7, 9], [15, 7, 9], or [7, 9]. Out of these, [15, 7, 9] gives the highest contribution with 15*(3) = 45. So f[4] = f[1] + 45 = 1 + 45 = 46.

  6. With i = 5 (arr[4] = 2), we consider [15, 7, 9, 2], [7, 9, 2], and [9, 2]. However, [9, 7, 2] is not considered since its length is greater than k. Choosing [9, 2] allows us to add 9*(2) to f[3], giving the largest sum. Therefore, f[5] = f[3] + 9*2 = 31 + 18 = 49.

  7. At i = 6 (arr[5] = 5), we consider [9, 2, 5], [2, 5], and [5]. The subarray [9, 2, 5] gives the maximum contribution with 9 * 3 = 27. So, f[6] = f[3] + 27 = 31 + 27 = 58.

  8. Finally, for i = 7 (arr[6] = 10), we consider [2, 5, 10], [5, 10], and [10]. [5, 10] yields the best result with 10 * 2 contribution, giving us f[7] = f[5] + 20 = 49 + 20 = 69.

So, the maximum sum that can be obtained from the array after completing this partition and modification process is f[7] = 69.

To recap, we solved this by iterating over each element, considering every possible partition that could end at that element within the constraint of k length, and choosing the one which maximizes the sum at each step while leveraging previously computed results.

Solution Implementation

1class Solution:
2    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
3        # Length of the given array
4        array_length = len(arr)
5      
6        # Initialize the dp (dynamic programming) array with 0's, 
7        # where dp[i] will be the max sum for the subarray arr[0:i]
8        dp = [0] * (array_length + 1)
9      
10        # Start from the first element and compute the max sum for each subarray
11        for i in range(1, array_length + 1):
12            max_element = 0  # To keep track of the maximum element in the current partition
13          
14            # Check partitions of lengths from 1 to k
15            for j in range(i, max(0, i - k), -1):
16              
17                # Update the maximum element in the current partition
18                max_element = max(max_element, arr[j - 1])
19              
20                # Update the dp table:
21                # dp[i] is the maximum of its previous value and the sum of the new partition
22                # The new partition sum is calculated by multiplying the size of the partition
23                # (i - j + 1) with the maximum element in that partition.
24                dp[i] = max(dp[i], dp[j - 1] + max_element * (i - j + 1))
25      
26        # Return the maximum sum for the entire array
27        return dp[array_length]
28```
29
30The updated code follows Python 3 standards, has standardized variable names that clearly describe their purposes, and contains comments that explain each step of the algorithm, hopefully making it clearer how the function works. Note that `List` should also be imported from `typing` module in the final code if not already in the script:
31
32```python
33from typing import List
34
1class Solution {
2
3    // Function to find the maximum sum after partitioning the array
4    public int maxSumAfterPartitioning(int[] arr, int k) {
5        // n is the length of the array
6        int n = arr.length;
7        // dp array to store the maximum sum at each partition
8        int[] dp = new int[n + 1];
9      
10        // Loop over the array elements
11        for (int i = 1; i <= n; ++i) {
12            // Initialize the maximum element in the current partition to zero
13            int maxInPartition = 0;
14            // Try all possible partitions of size up to k
15            for (int j = i; j > Math.max(0, i - k); --j) {
16                // Update the maximum element in this partition
17                maxInPartition = Math.max(maxInPartition, arr[j - 1]);
18                // Update dp[i] with the maximum sum using the maximum element times the size of the partition
19                // and compare it with the existing value in dp[i] to keep the max sum at each partition
20                dp[i] = Math.max(dp[i], dp[j - 1] + maxInPartition * (i - j + 1));
21            }
22        }
23        // Return the maximum sum after partitioning
24        return dp[n];
25    }
26}
27
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    int maxSumAfterPartitioning(vector<int>& arr, int k) {
8        int n = arr.size(); // Get the size of the array
9        vector<int> dp(n + 1, 0); // Create a dynamic programming table initialized with zeros
10
11        // Iterate over the array to fill the dp table
12        for (int i = 1; i <= n; ++i) {
13            int maxElement = 0; // Store the maximum element in the current partition
14          
15            // Try different partition lengths up to 'k'
16            for (int j = i; j > max(0, i - k); --j) {
17                // Update maxElement with the largest value in the current partition
18                maxElement = max(maxElement, arr[j - 1]);
19              
20                // Update the dp table by considering the best partition ending at position 'i'
21                dp[i] = max(dp[i], dp[j - 1] + maxElement * (i - j + 1));
22            }
23        }
24      
25        // Return the maximum sum after partitioning the last element
26        return dp[n];
27    }
28};
29
1// Function to calculate the maximum sum of subarrays after partitioning
2// arr: An array of integers
3// k: An integer that defines the maximum length of each partition
4function maxSumAfterPartitioning(arr: number[], k: number): number {
5    const n: number = arr.length; // The length of the input array
6    // Initialize an array to store the maximum sum of subarrays up to each index
7    const dp: number[] = new Array(n + 1).fill(0);
8
9    // Iterate through the array
10    for (let i = 1; i <= n; ++i) {
11        let maxElement: number = 0; // Variable to keep track of the max element in the current partition
12        // Check all possible partitions up to the length 'k'
13        for (let j = i; j > Math.max(0, i - k); --j) {
14            maxElement = Math.max(maxElement, arr[j - 1]); // Update max element of the current partition
15            // Update the dp array with the maximum sum by comparing the existing sum and
16            // the new sum formed by adding the max element multiplied by the partition size
17            dp[i] = Math.max(dp[i], dp[j - 1] + maxElement * (i - j + 1));
18        }
19    }
20    // Return the maximum sum after partitioning, which is stored at the end of dp array
21    return dp[n];
22}
23
Not Sure What to Study? Take the 2-min Quiz

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Time and Space Complexity

Time Complexity:

The time complexity of the given code is O(n * k). This is because the outer loop runs for n iterations (from 1 to n), where n is the length of the input array arr. The inner loop runs up to k times for each outer loop iteration, but no more than i times (down to max(0, i - k)). For each iteration of the inner loop, a constant amount of work is done: updating the maximum value in the current window (mx) and possibly updating the maximum sum f[i]. So, the total time taken is proportional to n * k.

Space Complexity:

The space complexity of the code is O(n) since it employs a one-dimensional array f with a size of n + 1 to store the maximum sum that can be obtained up to each index 0 to n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«