Minimum Difficulty of a Job Schedule

In this approach, we iterate over every position in the array and try to make a subarray till that index and recursively call the function on the rest of the array.

At every position, we know where the array starts from the arguments in the recursive function, so we calculate the maximum from the starting position of the current subarray and the position we are making the cut and add it to the recursive call on the rest of the array. We take the minimum of the places of possible sum and return the minimum sum.
 

We create a recursive function subarraySum(arr, startPos, splitRem), Where arr is the given array, startPos is the starting index of the current subarray, splitRem is the number of remaining splits.

Algorithm:

• In the function subarraySum(arr, startPos, splitRem)
  • If splitRem is 0
    • Return maximum value from index startPos to the last element in array ‘arr’
  • Set currArrMax as the negative infinity
  • Set minSubarraySum as infinity
  • Iterate index from startPos to size of arr - splitRem
    • Set num as arr[index]
    • Set currArrMax as maximum of itself and arr[index].
    • Set minSubarraySum as minimum of subarraySum(arr, index + 1, splitRem - 1)
  • Return minSubarraySum
• In the given function just return minSubarraySum(arr, 0, k - 1)

In this approach, we utilise the same technique as the last approach, but there are multiple recursive calls with the same parameters so, we will create a cache to store the results and avoid multiple recursive calls.

We create a recursive function subarraySum(arr, startPos, splitRem, cache), Where arr is the given array, startPos is the starting index of the current subarray, splitRem is the number of remaining splits.cache is the cache that stores the values of recursive calls.

Algorithm:

• In the function subarraySum(arr, startPos, splitRem, cache)
  • If splitRem is 0
    • Return maximum value from index startPos to the last element in array ‘arr’
  • Set splits as length of cache - splitRem
  • If cache[splits][startPos] doesn’t equal to -1 return it.
  • Set currArrMax as the negative infinity
  • Set minSubarraySum as infinity
  • Iterate index from startPos to size of arr - splitRem
    • Set num as arr[index]
    • Set currArrMax as maximum of itself and arr[index].
    • Set minSubarraySum as minimum of subarraySum(arr, index + 1, splitRem - 1)
  • Set cache[splits][startPos] as minSubarraySum
  • Return minSubarraySum
• In the given function
  • Create a 2D matrix, ‘cache’ of size (K - 1)x(length of arr), with all values as -1
  • Return minSubarraySum(arr, 0, k)

In this approach, we will use the stack to speed up things, because we don’t have to check every single cutoff position The stack keeps the index of monotonically decreasing number in A. When checking ARR[i], assuming that the last number that is larger than ARR[i] is ARR[t] (stack.top() = t after poping), there are two possible situations:

1. For possible cut off index m in ARR[t: i]: t <= m <i:
   We need to check for possible cut off. And the corresponding code is in the while loop: " j = stack.pop() dp2[i] = min(dp2[i], dp2[j] - ARR[j] + ARR[i])"
   Here we only check those items pop from the stack (they have a smaller index but larger value). we can see that the items pop before this loop were smaller, they were dominated by the items left in the stack. So we don't have to check those items.
2. For possible cut off index m in ARR[:t]: m < t
   since ARR[t] is the last number that larger than ARR[i], we know ARR[t] = max(ARR[t:i]), for any index m before t(m<t), we have max(ARR[m:i]) = max(ARR[m:t]) : we can directly "dp2[i] = min(dp2[i], dp2[stack.top()])"
    

Remember that in 2D Array: dp[k][i] means the min value in k subarrays for i elements, it equals dp[d][i] = dp[d][t] (t < i so dp[d][t] should have already been calculated)

Algorithm:

• Set n as the length of the ‘arr’
• Create two arrays currArr and nextArr of length equal to ‘ARR’, with infinity as values.
• Iterate split from 0 to k - 1
  • Create an empty stack ‘stack’
  • Iterate i from split to n - 1
    • Set nextArr[i] as currArr[i - 1] + arr[i] if i doesn’t equal to 0,otherwise arr[i]
    • While the length of the stack is not 0 and arr[top of stack] is not less than arr[i]
      • Set j as the top of the stack and pop the stack.
      • Set nextArr[i] as the minimum of itself and nextArr[j] + arr[i] + arr[i].
    • If the length of the stack is not 0
      • Set nextArr[i] as the minimum of itself and the top of stack
    • Insert i into the stack.
  • Swap currArr and nextArr
• Return the last element of currArr