# Maximum Strength of K Disjoint Subarrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-strength-of-k-disjoint-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/maximum-strength-of-k-disjoint-subarrays
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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.

# Approaches
## Naive Recursive Approach
This approach involves a direct translation of the problem's definition into a recursive function. The function explores all possible ways to partition the array into `k` disjoint subarrays and calculates the strength for each combination, returning the maximum one. It does not use any form of memoization, leading to exponential time complexity.
**Time:** Exponential, likely O(n^k) or worse. This is because the function branches out extensively without reusing results of solved subproblems. · **Space:** O(n + k) for the recursion stack depth.
**Pros:** Simple to understand and follows the problem definition directly.
**Cons:** Extremely inefficient due to a massive number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.; The recursion depth can be large, potentially leading to a stack overflow error for large `n` or `k`.
### Explanation
The core idea is to define a function, say `solve(i, j)`, which calculates the maximum strength considering the first `i` elements of `nums` and selecting exactly `j` subarrays. To compute `solve(i, j)`, we explore two main choices:

1.  **Don't use `nums[i-1]` in the `j`-th subarray**: The optimal solution for `j` subarrays must be found within the first `i-1` elements. This corresponds to a recursive call `solve(i-1, j)`.
2.  **The `j`-th subarray ends at `nums[i-1]`**: We iterate through all possible start indices `p-1` (from `0` to `i-1`) for this last subarray. For each `p`, the first `j-1` subarrays must be chosen from `nums[0...p-2]`. The strength is calculated by adding the strength from the first `j-1` subarrays (`solve(p-1, j-1)`) and the strength of the new `j`-th subarray (`C_j * sum(nums[p-1...i-1])`).

The function returns the maximum value found among all these possibilities. This method is conceptually simple but computationally expensive because it re-solves the same subproblems (`solve(i', j')` for smaller `i'` and `j'`) multiple times.

```java
// NOTE: This is a conceptual implementation and will TLE.
class Solution {
    long[] prefix;
    int n, k;
    long negInf = Long.MIN_VALUE / 2;

    public long maximumStrength(int[] nums, int k) {
        this.n = nums.length;
        this.k = k;
        
        this.prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        return solve(n, k);
    }

    private long solve(int i, int j) {
        if (j == 0) {
            return 0;
        }
        if (i < j) {
            return negInf;
        }

        long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1);

        // Case 1: j subarrays are within nums[0...i-2]
        long res = solve(i - 1, j);

        // Case 2: j-th subarray ends at i-1
        for (int p = j; p <= i; p++) {
            long prevStrength = solve(p - 1, j - 1);
            if (prevStrength > negInf) {
                long currentSum = prefix[i] - prefix[p - 1];
                res = Math.max(res, prevStrength + coeff * currentSum);
            }
        }
        
        return res;
    }
}
```
### Algorithm
- Define a recursive function `solve(i, j)` that computes the maximum strength using `j` subarrays from the prefix `nums[0...i-1]`.
- The base cases for the recursion are:
  - If `j == 0`, we have selected 0 subarrays, so the strength is 0.
  - If `i < j`, it's impossible to select `j` non-empty disjoint subarrays from `i` elements, so we return a very small number (negative infinity) to indicate an invalid state.
- For the recursive step `solve(i, j)`, consider two possibilities:
  1. The `j` subarrays are all contained within the prefix `nums[0...i-2]`. The strength in this case is `solve(i-1, j)`.
  2. The `j`-th subarray ends at index `i-1`. We must find the optimal starting position `p-1` for this subarray. We iterate `p` from `1` to `i`. The strength is `solve(p-1, j-1) + C_j * sum(nums[p-1...i-1])`, where `C_j` is the coefficient for the `j`-th subarray.
- The result of `solve(i, j)` is the maximum of all these possibilities.
- The final answer is `solve(n, k)`.

## Dynamic Programming with O(n^2 * k) Complexity
This approach improves upon the naive recursion by using dynamic programming to avoid recomputing subproblems. We use a 2D array, `dp[i][j]`, to store the maximum strength achievable from the first `i` elements using `j` subarrays. The solution can be implemented either top-down with memoization (by storing the results of the recursive calls) or bottom-up by filling the DP table iteratively. The state transition involves a nested loop, leading to a polynomial but still inefficient time complexity.
**Time:** O(n^2 * k) due to three nested loops. · **Space:** O(n * k) to store the DP table.
**Pros:** A significant improvement over naive recursion.; Guaranteed to find the optimal solution.; Systematic and easier to debug than a complex recursive solution.
**Cons:** The time complexity of O(n^2 * k) is too high for the given constraints and will likely result in a TLE.; The space complexity of O(n * k) can also be large, though it might fit within memory limits.
### Explanation
We define `dp[i][j]` as the maximum strength from `nums[0...i-1]` using `j` subarrays. The DP transition is as follows:

`dp[i][j] = max(dp[i-1][j], max_strength_ending_at_i)`

Here, `dp[i-1][j]` represents the case where the `j` subarrays are all within `nums[0...i-2]`. `max_strength_ending_at_i` is the maximum strength if the `j`-th subarray ends at `i-1`. This is calculated by trying all possible start points `p-1` for the last subarray:

`max_strength_ending_at_i = max_{1 <= p <= i} (dp[p-1][j-1] + C_j * sum(nums[p-1...i-1]))`

By pre-calculating prefix sums, `sum(nums[p-1...i-1])` can be found in O(1). The three nested loops (over `j`, `i`, and `p`) give this approach its `O(n^2 * k)` time complexity.

```java
import java.util.Arrays;

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long negInf = Long.MIN_VALUE / 2;
        long[][] dp = new long[n + 1][k + 1];
        for (long[] row : dp) {
            Arrays.fill(row, negInf);
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 0;
        }

        for (int j = 1; j <= k; j++) {
            long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1);
            for (int i = j; i <= n; i++) {
                // Case 1: j subarrays are in nums[0...i-2]
                long option1 = dp[i - 1][j];
                
                // Case 2: j-th subarray ends at i-1
                long maxStrengthEndingAtI = negInf;
                for (int p = j; p <= i; p++) {
                    // j-th subarray is nums[p-1...i-1]
                    // j-1 subarrays are in nums[0...p-2]
                    if (dp[p - 1][j - 1] > negInf) {
                        long currentSum = prefix[i] - prefix[p - 1];
                        maxStrengthEndingAtI = Math.max(maxStrengthEndingAtI, dp[p - 1][j - 1] + coeff * currentSum);
                    }
                }
                
                dp[i][j] = Math.max(option1, maxStrengthEndingAtI);
            }
        }

        return dp[n][k];
    }
}
```
### Algorithm
- Precompute the prefix sums of the `nums` array to quickly calculate subarray sums.
- Create a 2D DP table, `dp[i][j]`, to store the maximum strength using `j` subarrays from the prefix `nums[0...i-1]`.
- Initialize `dp[i][0] = 0` for all `i` (0 strength for 0 subarrays) and other `dp` entries to negative infinity.
- Iterate through the number of subarrays `j` from `1` to `k`.
- For each `j`, iterate through the array index `i` from `1` to `n`.
- The value `dp[i][j]` is the maximum of two cases:
  1. The `j` subarrays are chosen from `nums[0...i-2]`, so the value is `dp[i-1][j]`.
  2. The `j`-th subarray ends at index `i-1`. We find the best starting index `p-1` by iterating `p` from `1` to `i`. The strength is `dp[p-1][j-1] + C_j * (prefix[i] - prefix[p-1])`.
- After filling the table, `dp[n][k]` holds the final answer.

## Optimized Dynamic Programming
This is the most efficient approach, which optimizes the `O(n^2 * k)` DP solution. By rewriting the DP recurrence, we can observe that the inner loop, which iterates to find the best split point, is redundant. Its result can be calculated in O(1) time by maintaining a running maximum. This optimization reduces the time complexity to `O(n * k)`. Additionally, space can be optimized to `O(n)` since computing the DP values for `j` subarrays only requires the values for `j-1` subarrays.
**Time:** O(n * k), because of the two nested loops over `j` (subarrays) and `i` (elements). · **Space:** O(n), as we only need to store DP states for the current and previous number of subarrays.
**Pros:** Highly efficient with O(n * k) time complexity, which passes the given constraints.; Optimal space complexity of O(n).; Provides a structured way to solve a complex optimization problem.
**Cons:** The logic is more complex and less intuitive than the straightforward DP approach.; Requires careful handling of indices and state transitions to implement correctly.
### Explanation
The key to optimization lies in the recurrence relation for `dp[i][j]`. The term for calculating the max strength with the `j`-th subarray ending at `i-1` is:

`max_{1 <= p <= i} (dp[p-1][j-1] + C_j * (prefix[i] - prefix[p-1]))`

We can rearrange this to:

`C_j * prefix[i] + max_{1 <= p <= i} (dp[p-1][j-1] - C_j * prefix[p-1])`

As we iterate `i` from `1` to `n` (for a fixed `j`), the term `max_{1 <= p <= i} (...)` can be updated in O(1) time. We maintain a variable, `max_prev_term`, that keeps track of the maximum value of `dp[p-1][j-1] - C_j * prefix[p-1]` seen so far. This eliminates the innermost loop over `p`, bringing the time complexity down to `O(n * k)`. The space is optimized by noticing that `dp[...][j]` only depends on `dp[...][j-1]`, so we only need to store the DP states for the current and previous number of subarrays.

```java
import java.util.Arrays;

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        long[] dp = new long[n + 1];
        long negInf = Long.MIN_VALUE / 2; 

        for (int j = 1; j <= k; j++) {
            long[] prevDp = dp;
            dp = new long[n + 1];
            Arrays.fill(dp, negInf);
            
            long maxPrevTerm = negInf;
            long coeff = (long)(k - j + 1) * (j % 2 == 1 ? 1 : -1);

            for (int i = j; i <= n; i++) {
                // Update the running maximum of (prev_dp[p-1] - coeff * prefix[p-1]) for p up to i
                if (prevDp[i - 1] > negInf) {
                    maxPrevTerm = Math.max(maxPrevTerm, prevDp[i - 1] - coeff * prefix[i - 1]);
                }

                // Calculate max strength with j-th subarray ending at i-1
                if (maxPrevTerm > negInf) {
                    long strengthEndingAtI = coeff * prefix[i] + maxPrevTerm;
                    dp[i] = Math.max(dp[i - 1], strengthEndingAtI);
                } else {
                    dp[i] = dp[i-1];
                }
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- Precompute the prefix sums of the `nums` array.
- Use two arrays, `dp` and `prev_dp`, of size `n+1` to store the DP states for the current (`j`) and previous (`j-1`) number of subarrays, respectively. This optimizes space from O(n*k) to O(n).
- Initialize `prev_dp` (for `j=0`) with all zeros.
- Loop `j` from `1` to `k`:
  - Inside the loop, calculate the coefficient `C_j`.
  - Initialize a variable `max_prev_term` to negative infinity. This will track the running maximum of the optimized term.
  - Loop `i` from `1` to `n`:
    - Update `max_prev_term = max(max_prev_term, prev_dp[i-1] - C_j * prefix[i-1])`.
    - Calculate the maximum strength with the `j`-th subarray ending at `i-1`: `strength_ending_at_i = C_j * prefix[i] + max_prev_term`.
    - Update `dp[i] = max(dp[i-1], strength_ending_at_i)`.
  - After the inner loop, `prev_dp` is updated to `dp` for the next iteration of `j`.
- The final answer is the last element of the `dp` array after `k` iterations, `dp[n]`.

# Solutions
### Java

```java
class Solution {
public
  long maximumStrength(int[] nums, int k) {
    int n = nums.length;
    long[][][] f = new long[n + 1][k + 1][2];
    for (int i = 0; i <= n; i++) {
      for (int j = 0; j <= k; j++) {
        Arrays.fill(f[i][j], Long.MIN_VALUE / 2);
      }
    }
    f[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
      int x = nums[i - 1];
      for (int j = 0; j <= k; j++) {
        long sign = (j & 1) == 1 ? 1 : -1;
        long val = sign * x * (k - j + 1);
        f[i][j][0] = Math.max(f[i - 1][j][0], f[i - 1][j][1]);
        f[i][j][1] = Math.max(f[i][j][1], f[i - 1][j][1] + val);
        if (j > 0) {
          long t = Math.max(f[i - 1][j - 1][0], f[i - 1][j - 1][1]) + val;
          f[i][j][1] = Math.max(f[i][j][1], t);
        }
      }
    }
    return Math.max(f[n][k][0], f[n][k][1]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumStrength(vector<int> &nums, int k) {
    int n = nums.size();
    long long f[n + 1][k + 1][2];
    memset(f, -0x3f3f3f3f3f3f3f3f, sizeof(f));
    f[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
      int x = nums[i - 1];
      for (int j = 0; j <= k; j++) {
        long long sign = (j & 1) == 1 ? 1 : -1;
        long long val = sign * x * (k - j + 1);
        f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1]);
        f[i][j][1] = max(f[i][j][1], f[i - 1][j][1] + val);
        if (j > 0) {
          long long t = max(f[i - 1][j - 1][0], f[i - 1][j - 1][1]) + val;
          f[i][j][1] = max(f[i][j][1], t);
        }
      }
    }
    return max(f[n][k][0], f[n][k][1]);
  }
};

```

### Python

```python
class Solution : def maximumStrength ( self , nums : List [ int ], k : int ) -> int : n = len ( nums ) f = [[[ - inf , - inf ] for _ in range ( k + 1 )] for _ in range ( n + 1 )] f [ 0 ][ 0 ][ 0 ] = 0 for i , x in enumerate ( nums , 1 ): for j in range ( k + 1 ): sign = 1 if j & 1 else - 1 f [ i ][ j ][ 0 ] = max ( f [ i - 1 ][ j ][ 0 ], f [ i - 1 ][ j ][ 1 ]) f [ i ][ j ][ 1 ] = max ( f [ i ][ j ][ 1 ], f [ i - 1 ][ j ][ 1 ] + sign * x * ( k - j + 1 )) if j : f [ i ][ j ][ 1 ] = max ( f [ i ][ j ][ 1 ], max ( f [ i - 1 ][ j - 1 ]) + sign * x * ( k - j + 1 ) ) return max ( f [ n ][ k ])
```