Split Array

In this approach, we will create a recursive function; at each step, we will try to split the array at every position available position, then we will take the sum of the left half of the split and call the recursive function on the right half of the array. We will create a function recursiveSplit(arrRem, currentM), where arrRem is the current array, and currentM is the remaining subarrays to be formed.
 

Algorithm:

• In the function recursiveSplit(arrRem, currentM)
  • If length of arrRem is 0, return 0
  • If currentM is 1 return sum of arrRem
  • Set minResult as infinity
  • Iterate j from 1 to length of arrRem
    • Set leftSum as the sum of elements of arrRem from index 0 to j - 1
    • Call the recursiveSplit function on the array of elements with index from j in arrRem and currentM - 1 and set it as rightSum
    • rightSum as recursiveSplit(arrRem[j: ], currentM - 1)
    • Update minResult as minimum of minResult and sum of leftSum and rightSum
  • Return minResult
• Return recursiveSplit(arr, m)

In this approach, we will try to optimize the previous solution. We can create a matrix and store the solution for each starting index of each subarray, the array ARR, and M’s value. 

We try to split the array at every possible index and calculate the leftSum and rightSum.

We can do one more optimisation, i.e., calculate the sum of the left half of the subarray at each iteration. We can maintain a cumulative sum array, where the ith index contains the sum 0th to ith.

So if we want to find the sum of the left half of a subarray starting ith and split at the index jth, it will be cumilativeSum[i + j] - cumulativeSum[i]
 

We will create a function recursiveSplit(currentIndex, currentM), where currentIndex is the starting index of the current array, and currentM is the remaining subarrays to be formed.

Algorithm:

• Initialise an empty array cumulativeSum array
• Create the cumulativeSum array by inserting the sum of each element of arr and the last element of cumulativeSum
• Create a 2D matrix  memo of size length of array x currentM
• In the function recursiveSplit(currentIndex, currentM)
  • If currentIndex is 0 return 0
  • If currentM is 1, return the of arr from index currentIndex
  • If currentIndex is in memo and currentM is memo[currentIndex]
    • Return currentIndex[currentIndex][currentM]
  • Iterate j from 1 to size of arr
    • Set leftSum as cumilativeSum[currentIndex + j] - cumilativeSum[currentIndex]
    • Set rightSum as recursiveSplit(currentIndex + j, currentM - 1)
    • Set memo[currentIndex][currentM] as minimum of itself and leftSum + rightSum
    • If leftSum is greater than rightSum break the loop
  • Return memo[currentIndex][currentM]
• Return recursiveSplit(0, m)

In this approach, it can be noted that the minimum possible solution is the maximum value of the array when every element of the array is a separate subarray for any array.

It can also be observed that the maximum possible solution for an array is the sum of all elements in the array when no splits in the array will occur.

So we can write a binary search by taking the lower as the maximum value and the higher as the sum of all the elements. Then for each solution, we check if the number of splits is not greater than M, then it’s a valid answer, and we will take the minimum of the valid answers.

We create a function, isValidSplit(arr, m, ans), here arr is the given array, m is the allowed no. of subarrays, and ans the solution we are checking currently.

Algorithm:

• In the function isValidSplit(arr, m, ans)
  • Set splits and currSum as 0
  • Iterate num through arr
    • Add num into currSum
    • If currSum is greater than ans
      • Increase splits by 1 
      • Set currSum as num
  • If splits are not greater than m return true otherwise, return false.
• Set ans as -1
• Set low as the maximum value in arr
• Set high as the sum of all elements of the arr
• If low is less than high
  • Set mid as low + high / 2
  • If isValidSplit(arr, m, mid)
    • Set ans as mid
    • Set high as mid - 1
  • Otherwise, set low as mid
• Return ans