Partition Array for Maximum Sum

The basic idea is to check for every possible valid way of dividing the array and find the max of all valid ways.  

For each index ‘i’ we have options of taking a subarray of length [1,2,..,k] from’ i‘ (including ‘i’).

Let’s say we take a subarray starting from ‘i’ and ending to ‘j’ then find the maximum element of the subarray [i,j] let it be ‘max’ so the contribution of this subarray to the final sum will be (j-i+1)*max.

Let the function maxSubarray(i, n, num, k)( ‘i’ is the current index of the array, n is the size of the array, num is the given array, k is the max size of the subarray) give the maximum sum of the subarray [i,n-1],(consider 0-based indexing here) after partitioning. So the final answer will be maxSubarray(0, n, num, k).

Here is the algorithm:

• In the function maxSubarray(i, n, num, k)
  • If ‘i’ is equal to n
    • return 0
  • Initialize three variables m = INT_MIN , ans = INT_MIN , j = i.
    • Iterate from j=i to j<min(i+k,n)
      • m=max(m,num[j])
      • Update ans as max(ans,maxSubarray(j+1,n,num,k) + m*(j-i+1)).
  • Return ans

• given function:
  • Declare an integer variable n and initialize it as the size of the array.
  • Return maxSubarray(0, n, num, k).

The basic idea is to store the results of the recursive calls to avoid repetition. We can memorize the results of our function calls in an array (say, ‘DP’). The definition of the function “maxSubarray” will remain the same. For each index will be checked whether we have already computed answer for ‘i’ or not if we have the answer then we will simply return it otherwise

We have to compute the answer for index ‘i’ as discussed in the brute force method.

For each index ‘i’ we have options of taking a subarray of length [1,2,..,k] from’ i‘ (including ‘i’).

Let say we take a subarray starting from ‘i’ and ending to ‘j’ then find the maximum element of the subarray [i,j] let it be ‘max’ so the contribution of this subarray to the final sum will be (j-i+1)*max.

Here is the algorithm:

• In the function maxSubarray(i, n, num, k,dp)
  • If ‘i’ is equal to n
    • return 0.
  • If dp[i]!=-1
    • return dp[i].
  • Initialize three variables m = INT_MIN , ans = INT_MIN , j = i.
    • Iterate from j = i to j < min(i+k,n)
      • m = max( m, num[j] )
      • Update ans as ans = max(ans, maxSubarray(j+1, n, num, k) + m*(j-i+1))
    • Store the answer in dp as dp[i]=ans
  • Return ans

• given function:
  • Declare an integer variable n and initialize it as the size of the array.
  • Declare an array “dp” of size n and initialize it with -1.
  • Return maxSubarray(0, n, num, k,dp).

The idea is similar to the previous approach. In this approach, we use an iterative way to store the count of answers for each index ‘i’ using previously computed values.  

Let's define dp[i] as the maximum sum of the subarray [0,i] after partitioning. So our final answer will be dp[n-1].

For each index ‘i’ we can iterate over all the possible starting points of the subarray ending with ‘i’ lets say that index is ‘j’ so 

dp[i]=(max element in subarray [j,i])*(i-j+1) + dp[j-1] (if j-1>=0).

Here is the algorithm :

• Create a 1-d array of size ‘n’ initialized with INT_MIN.
• Run a loop from 0 to n-1 (say, iterator ‘i’)
  • Let’s define a variable m, initially equals to INT_MIN (this will contain the maximum value between the subarray [j,i]
  • Run a loop from ‘i’ to ‘i’-’k’+1 (say, iterator ‘j’)
    • m=max(m,arr[j])
    • if(j-1>=0)
      • Update dp[i] as max(dp[i], m * (i-j+1) + dp[j-1])
    • Else
      • Update dp[i] as max(dp[i], m * (i-j+1))
• Return dp[n-1]