3077. Maximum Strength of K Disjoint Subarrays

HardArrayDynamic ProgrammingPrefix Sum
Leetcode Link

Problem Description

In this problem, we are given an array nums with n integers and a positive odd integer k. We must find k disjoint (non-overlapping) subarrays from nums such that their collective 'strength' is maximized. The 'strength' is a calculated value based on the individual sums of the selected subarrays. Each subarray's sum is alternately subtracted and added, starting with addition, and multiplied by a decreasing value starting with x for the first sum, x - 1 for the second sum, and so forth, until reaching 1 for the last sum.

The rules for calculating 'strength' are as follows:

  • First, we define the sum of an 'i-th' subarray as sum[i].
  • Then, we calculate the 'strength' by alternatingly adding and subtracting the products of sum[i] and (x - i + 1) for i ranging from 1 to x, where x is the subarray index in our calculation.

Our goal is to select the subarrays in such a way that the sum of their strengths is the largest possible. The selection doesn't have to cover the entire array.

The challenge is to devise an algorithm that can efficiently find this optimal selection of subarrays to maximize strength.

Intuition

The intuition behind solving this problem lies in recognizing it as a dynamic programming challenge. Dynamic programming is often used for optimization problems where decisions have to be made sequentially and the problem can be broken down into subproblems that retain the same structure as the original one.

To approach the problem, we consider the two states for each element in the array: whether it is included in the current subarray (increasing the strength) or not. This derives from the understanding that the strength of any given subarray is based on the sum of its elements, and the position of each element affects its contribution to the overall strength.

However, since we deal with k subarrays instead of one, and each subarray contributes differently to the total strength, we also need to factor in the subarray index. The decision to include a number in a subarray or not affects the strength differently based on whether it's part of an even or odd-indexed subarray due to alternating multiplication.

From this, we arrive at a solution approach using dynamic programming. We maintain two choices for each number: to include it in a subarray or not, and we calculate the corresponding strength. This leads to a 3D state representation. The first dimension represents the number of available elements from the start of the array, the second dimension represents the number of subarrays chosen so far, and the third dimension represents the state of inclusion of the current element.

We dynamically build the optimal solutions from the ground up, starting with no elements selected and no subarrays. As we progress, we update the values based on the choices that yield the highest strength. The transition between states is determined by the aforementioned considerations.

Ultimately, the solution will be found at the state where all elements have been considered, and k subarrays have been formed. The answer will be the maximum possible strength within this state, which reflects the maximum strength that can be obtained from any k disjoint subarrays within the given array.

Learn more about Dynamic Programming and Prefix Sum patterns.

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

How does merge sort divide the problem into subproblems?

Solution Approach

The problem is addressed using dynamic programming, which involves breaking the problem into smaller, easier-to-manage subproblems. We create a 3D array f which will be used to store our dynamic programming states. The size of this array is (n+1) x (k+1) x 2, where n is the length of the given array nums, k is the number of subarrays we wish to choose, and the last dimension stores whether the i-th number is selected in the subarray (1) or not (0).

Here's a step-by-step explanation of the solution approach:

  1. Initialize a 3D array f with dimensions (n+1) x (k+1) x 2, filled with negative infinity (-inf) to represent the minimum possible strength values. We use negative infinity as we're looking to maximize the strength, and initially, we have no subarrays, so the maximum strength should start very low.

  2. Set f[0][0][0] to 0, as no strength is gained without selecting any subarrays or numbers.

  3. Iterate through each element x in nums, starting from the index 1 to include a 0-index case (representing no element has been chosen yet).

  4. For each element, iterate over the number of subarrays j from 0 to k. The variable j represents how many subarrays have been selected up to the current index.

  5. Calculate the sign as 1 if j is odd and -1 if j is even, as the strength should alternate between adding and subtracting for each subarray.

  6. Then, compute the maximum strength when the i-th element is not included in the subarray with f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]). This takes the maximum between the previous element's strength when it's not included and when it's included.

  7. After that, if j is greater than 0, update the maximum strength when the i-th element is included in a subarray with:

    • f[i][j][1] = max(f[i][j][1], f[i - 1][j][1] + sign * x * (k - j + 1)) if the i-th element is continuing the current subarray.
    • f[i][j][1] = max(f[i][j][1], max(f[i - 1][j - 1]) + sign * x * (k - j + 1)) if the i-th element starts a new subarray.

  8. Continue iterating through all elements and updating the 3D array f until it represents the maximum strength values for each possible number of subarrays chosen.

  9. The final answer is the maximum of f[n][k][0] and f[n][k][1], which represents the maximum strength achieved either by including or not including the last element in the k-th subarray.

This implementation carefully accounts for the alternating sign of the contribution of each element depending on the position within the overall strength calculation. It also smartly navigates the decision of starting a new subarray or continuing the current one, which is the crux of optimizing the overall strength.

The use of dynamic programming in this solution exploits the nature of the problem's overlapping subproblems and the necessity of making decisions based on the current state and the state of previous choices.

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

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we have the following input parameters:

  • nums = [4, 1, -5, 2, -1, 3]
  • k = 3 (we need to find 3 disjoint subarrays)
  • x = 3 (the starting multiplier for the strength calculation)

Now, we need to use the dynamic programming approach described in the content to find the maximum strength. Let's go through the steps:

  1. We initialize a 3D array f to store the strength of the various states, with default values of negative infinity since we aim to maximize strength. This 3D array has the size (7 x 4 x 2) because n = 6 and we add 1 to account for the possibility of selecting no numbers.

  2. We set f[0][0][0] to 0 since no numbers have been selected and the initial strength is 0.

  3. We start iterating through the numbers starting from (index 1):

    • For i = 1 with nums[i - 1] = 4. Since a subarray starts with this element or it's a single element subarray, the maximum strength up to this point would be f[1][1][1] = 4 * 3 because j = 1 and x = 3. We are multiplying by x - j + 1 = 3.

  4. We proceed with the next elements, keeping in mind the alternating addition and subtraction for the strength and update the f array:

    • i = 2, nums[i - 1] = 1. If we start another subarray, it would decrease the strength since it needs to be subtracted now. Consequently, we would simply carry over the max strength from the previous step if we do not start a new subarray here.

  5. As we continue, we account for updating both cases: including and not including the current number in a subarray. Let's demonstrate a few updates:

    • For i = 3, nums[i - 1] = -5, we should not add it to an existing subarray as it reduces the sum, so f[i][j][1] would not be considered.

    • Continuing for i = 4, nums[i - 1] = 2. If it's in a new subarray as the second chosen subarray (j = 2), the strength would be subtracted, so we would have to consider if it's beneficial to start a new subarray or not and compute accordingly.

  6. The calculation of the signs (1 for odd j and -1 for even j) and multipliers (k - j + 1) is part of the dynamic programming update equation at each step.

  7. By the time we've considered each element for either starting a new subarray or going into an existing one, our f array will have been populated with the maximum strength values for all the considered states.

  8. The final answer is the maximum of f[6][3][0] and f[6][3][1], as we have 6 numbers and we want the maximum achievable strength from 3 disjoint subarrays.

Let's assume that during the dynamic programming sequence the optimal disjoint subarrays chosen are [4], [-5, 2], and [3]. For this example, the strength would be calculated as (4*3) + (-5*2 + 2*2) + (3*1) = 12 - 6 + 3 = 9. The dynamic programming approach would explore several possibilities and find the optimal selection of disjoint subarrays for maximizing the total strength.

Solution Implementation

1class Solution:
2    def maximumStrength(self, nums: List[int], k: int) -> int:
3        # The length of the nums list
4        n = len(nums)
5        # Initialising a 3D dp array with negative infinity
6        dp = [[[-float('inf'), -float('inf')] for _ in range(k + 1)] for _ in range(n + 1)]
7        # Base case: the strength is 0 when no elements are chosen
8        dp[0][0][0] = 0
9      
10        # Iterate over the numbers in nums
11        for i, x in enumerate(nums, 1):
12            # Iterate over the potential number of changes to be made
13            for j in range(k + 1):
14                # Alternating sign based on even/odd value of j
15                sign = 1 if j % 2 == 1 else -1
16              
17                # Update dp: choose not to take the current number
18                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1])
19              
20                # Update dp: take the current number and add its strength
21                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + sign * x * (k - j + 1))
22              
23                # If it's possible to increase the number of changes made,
24                # consider the maximum of the previous state
25                if j > 0:
26                    dp[i][j][1] = max(
27                        dp[i][j][1], max(dp[i - 1][j - 1]) + sign * x * (k - j + 1)
28                    )
29      
30        # Return the maximum value from the last row and 'k' columns, considering both taking or not taking the last number
31        return max(dp[n][k])
32
33# Note: The replacement of `-inf` with `-float('inf')` ensures Python 3 compatibility.
34# The enumeration now properly uses 'enumerate()' function with a starting index of 1.
35# The name 'f' for the dynamic programming table has been replaced with 'dp' for clarity, which generally stands for "dynamic programming".
36
1import java.util.Arrays;
2
3class Solution {
4    // Method to calculate the maximum strength possible with the given parameters
5    public long maximumStrength(int[] nums, int k) {
6        int n = nums.length;
7        // dp is a 3-dimensional array for dynamic programming
8        // dp[position][usedK][isChosen] represents:
9        // - position: the current position in the nums array
10        // - usedK: the number of 'k' operations used
11        // - isChosen: a binary flag that tracks whether an element at the current position has been chosen (1) or not (0).
12        long[][][] dp = new long[n + 1][k + 1][2];
13
14        // Initialize all values to a very low number to avoid influence during max calculations
15        for (int i = 0; i <= n; i++) {
16            for (int j = 0; j <= k; j++) {
17                Arrays.fill(dp[i][j], Long.MIN_VALUE / 2);
18            }
19        }
20
21        // Starting condition: no elements chosen, no k used, strength is 0
22        dp[0][0][0] = 0;
23      
24        for (int i = 1; i <= n; i++) {
25            // x is the current element from nums array
26            int x = nums[i - 1];
27            for (int j = 0; j <= k; j++) {
28                // Calculate the sign based on parity of 'j'
29                long sign = (j & 1) == 1 ? 1 : -1;
30                // value to add/subtract to the current strength based on k
31                long value = sign * x * (k - j + 1);
32              
33                // Case where the current number is not chosen
34                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1]);
35              
36                // Case where the current number is chosen
37                dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][1] + value);
38              
39                // If we can use one more k, choose the best between the current and the previous state + value
40                if (j > 0) {
41                    long temp = Math.max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + value;
42                    dp[i][j][1] = Math.max(dp[i][j][1], temp);
43                }
44            }
45        }
46      
47        // Return the max strength from the final position with all k operations used,
48        // regardless of whether the last number is chosen or not.
49        return Math.max(dp[n][k][0], dp[n][k][1]);
50    }
51}
52
1#include <vector>
2#include <cstring>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    // Define a function to find the maximum strength of a sequence with operations
10    long long maximumStrength(vector<int>& nums, int k) {
11        int n = nums.size();
12        // Initialize a 3D vector for dynamic programming
13        vector<vector<vector<long long>>> dp(
14            n + 1,
15            vector<vector<long long>>(
16                k + 1,
17                vector<long long>(2, LLONG_MIN)
18            )
19        );
20        // Base case: no operations performed and no numbers to pick from, strength is 0
21        dp[0][0][0] = 0;
22
23        // Iterate over the numbers
24        for (int i = 1; i <= n; ++i) {
25            int x = nums[i - 1];
26            // Iterate over the number of operations
27            for (int j = 0; j <= k; ++j) {
28                // Determining sign based on the number of operations
29                long long sign = (j & 1) == 1 ? 1 : -1;
30                // Calculating the value to add/subtract for the current operation
31                long long val = sign * x * (k - j + 1);
32
33                // Do not perform a new operation: take the max strength from the previous state
34                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
35
36                // Continue with the operation or start a new operation if j > 0
37                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][1] + val);
38                if (j > 0) {
39                    // Consider adding the current value to previous maxes
40                    long long t = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1]) + val;
41                    dp[i][j][1] = max(dp[i][j][1], t);
42                }
43            }
44        }
45        // Return the maximum between not doing or doing the kth operation
46        return max(dp[n][k][0], dp[n][k][1]);
47    }
48};
49
1// Returns the maximum strength of a list by selecting numbers under certain conditions
2// nums: the list of numbers to be selected from
3// k: the number of selections allowed
4function maximumStrength(nums: number[], k: number): number {
5    // Get the number of elements in 'nums'
6    const numElements: number = nums.length;
7
8    // Initialize DP table with array dimensions based on 'numElements' and 'k'
9    // The DP table keeps track of the maximum strength value considering the selections made until now
10    // Each state has two possibilities: selected(-Infinity) or not-selected(-Infinity)
11    const dp: number[][][] = Array.from({ length: numElements + 1 }, () =>
12        Array.from({ length: k + 1 }, () => [-Infinity, -Infinity]),
13    );
14
15    // Base case: no numbers selected, strength is 0
16    dp[0][0][0] = 0;
17
18    // Iterate through all numbers
19    for (let i = 1; i <= numElements; i++) {
20        // Value of the current element
21        const currentValue: number = nums[i - 1];
22
23        // Iterate through all possible selections from 0 to k
24        for (let j = 0; j <= k; j++) {
25            // Sign is positive if 'j' is odd, negative if even
26            const sign: number = (j & 1) === 1 ? 1 : -1;
27            // Calculate value that will be added if the current number is selected
28            const val: number = sign * currentValue * (k - j + 1);
29
30            // Updates for state when current number is not selected
31            // It carries forward the maximum from the previous state's selected or not-selected value
32            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1]);
33
34            // Updates for state when current number is selected
35            dp[i][j][1] = Math.max(dp[i][j][1], dp[i - 1][j][1] + val);
36            if (j > 0) {
37                // Additionally check if transitioning from previous state with one less selection
38                dp[i][j][1] = Math.max(dp[i][j][1], Math.max(...dp[i - 1][j - 1]) + val);
39            }
40        }
41    }
42
43    // Return the maximum strength value achievable
44    return Math.max(...dp[numElements][k]);
45}
46
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n * k) where n is the length of the array nums and k is the given integer with which we are performing operations. This complexity arises from the nested for loop structure where the outer loop runs for n iterations (representing the length of the array nums) and the inner loop runs for k + 1 iterations (representing all values from 0 to k), resulting in a total of n * (k + 1) which is approximately O(n * k) when k is large.

Space Complexity

As for the space complexity, it is also O(n * k) because of the 3D list f that is being used to store computed values. The dimensions of this list are (n + 1) * (k + 1) * 2, effectively making the space used proportional to the size of the input array and the value of k. This space is required to keep track of the computed values for the function at each combination of index i in the array nums and the number of operations j up to k, with an additional dimension for the two scenarios (either adding or not adding the current element x to the sum).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

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

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 👨‍🏫