Check if it is Possible to Split Array

• Create a 2D boolean array dp[n][n], where dp[i][j] will store true if the subarray nums[i...j] can be fully split, and false otherwise.
• To handle subarray sum calculations efficiently, precompute a prefixSum array.
• The base cases for the DP are subarrays of length 1. dp[i][i] is true for all i from 0 to n-1, as a single-element array is already considered split.
• Iterate through all possible subarray lengths, from len = 2 to n.
• For each length, iterate through all possible starting indices i.
• For each subarray nums[i...j] (where j = i + len - 1), try every possible split point k from i to j-1.
• A split at k divides nums[i...j] into nums[i...k] and nums[k+1...j].
• This split is valid if both resulting subarrays are "good". A subarray is good if its length is 1 or its sum is greater than or equal to m.
• If the split is valid, we then check if the subarrays themselves can be further split by looking up our DP table: dp[i][k] and dp[k+1][j].
• If we find any k for which the split is valid and both subproblems are solvable, we set dp[i][j] = true and break the inner loop (since we've found one way to split nums[i...j])
• The final answer is the value of dp[0][n-1].

We can use a 2D DP table, dp[i][j], to store whether the subarray nums[i...j] is splittable. We can build this table bottom-up, starting from smaller subarrays and building up to the entire array.

• State: dp[i][j] = true if nums[i...j] can be split, false otherwise.
• Base Case: For any subarray of length 1, dp[i][i] = true.
• Transition: To compute dp[i][j], we iterate through all possible split points k from i to j-1. A split at k is possible if:
  1. The split itself is valid: The left part nums[i...k] is "good" AND the right part nums[k+1...j] is "good". An array is good if its length is 1 or its sum is >= m.
  2. The resulting subarrays can be fully split: dp[i][k] is true AND dp[k+1][j] is true.

If we find any such k, then dp[i][j] becomes true. To avoid recomputing subarray sums repeatedly, we can use a prefix sum array.

1class Solution {2    public boolean canSplitArray(List<Integer> nums, int m) {3        int n = nums.size();4        if (n <= 2) {5            return true;6        }7 8        long[] prefixSum = new long[n + 1];9        for (int i = 0; i < n; i++) {10            prefixSum[i + 1] = prefixSum[i] + nums.get(i);11        }12 13        boolean[][] dp = new boolean[n][n];14 15        for (int i = 0; i < n; i++) {16            dp[i][i] = true;17        }18 19        for (int len = 2; len <= n; len++) {20            for (int i = 0; i <= n - len; i++) {21                int j = i + len - 1;22                for (int k = i; k < j; k++) {23                    // Split into [i...k] and [k+1...j]24                    long leftSum = prefixSum[k + 1] - prefixSum[i];25                    boolean isLeftGood = (k - i + 1 == 1) || (leftSum >= m);26 27                    long rightSum = prefixSum[j + 1] - prefixSum[k + 1];28                    boolean isRightGood = (j - k == 1) || (rightSum >= m);29 30                    if (isLeftGood && isRightGood) {31                        if (dp[i][k] && dp[k+1][j]) {32                            dp[i][j] = true;33                            break;34                        }35                    }36                }37            }38        }39 40        return dp[0][n - 1];41    }42}

• First, handle the edge cases. If the array length n is 1 or 2, it's always possible to split, so return true.
• If n > 2, the key insight is that the array can be fully split if and only if there exists at least one pair of adjacent elements whose sum is greater than or equal to m.
• Iterate through the array from i = 0 to n-2.
• In each iteration, check if nums[i] + nums[i+1] >= m.
• If this condition is met for any i, it means we found a valid starting point for a sequence of splits, so we can immediately return true.
• If the loop completes without finding such a pair, it's impossible to perform the necessary splits, so return false.

This approach simplifies the problem by identifying a necessary and sufficient condition for an array to be splittable.

Base Cases:

• If n = 1, the array is already split. true.
• If n = 2, we can split [a, b] into [a] and [b]. Both are good (length 1), so the split is valid. true.

Core Insight (for n > 2): If there exists at least one pair of adjacent elements nums[i] and nums[i+1] such that their sum is >= m, we can guarantee a full split is possible. Here's why:

1. We can think of the split process in reverse: merging elements. We start with n individual elements.
2. If nums[i] + nums[i+1] >= m, we can merge them to form a block B. The reverse operation, splitting B into [nums[i]] and [nums[i+1]], is valid because both [nums[i]] and [nums[i+1]] are good (length 1), and the array they form, [nums[i], nums[i+1]], is also good because its sum is >= m.
3. Now we have n-1 items, including the block B. We can merge B with an adjacent element, say nums[i-1]. The new block B' has sum = sum(B) + nums[i-1] >= m + nums[i-1], which is also >= m. So, B' is a good block.
4. This process can be continued, merging the growing 'good' block with all other elements one by one. Each merge corresponds to a valid split in reverse.

Therefore, for n > 2, we only need to check for the existence of one such adjacent pair.

1class Solution {2    public boolean canSplitArray(List<Integer> nums, int m) {3        int n = nums.size();4        if (n <= 2) {5            return true;6        }7        8        for (int i = 0; i < n - 1; i++) {9            if (nums.get(i) + nums.get(i+1) >= m) {10                return true;11            }12        }13        14        return false;15    }16}