Maximum Strength of K Disjoint Subarrays

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.

• 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).

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.

// 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;
    }
}