Partition Array for Maximum Sum

Moderate
0/80
profile
Contributed by
28 upvotes
Asked in companies
SamsungHCL Technologies

Problem statement

You are given an array 'arr' of 'n' integers.


You have to divide the array into some subarrays such that each element is present in exactly one of the subarrays.


The length of each subarray should be at most 'k'. After partitioning all the elements of each subarray will be changed to the maximum element present in that subarray.


Find the maximum possible sum of all the elements after partitioning.


Note:

Input is given such that the answer will fit in a 32-bit integer.


Example: 
Input: 'k' = 3, 'arr' = [1, 20, 13, 4, 4, 1]

Output: 80

Explanation:
We can divide the array into the following subarrays
[1,20] max of this subarray is 20 so the contribution of 
this subarray in the final answer will be 20*2=40.
[13,4,4]  max of this subarray is 13 so the contribution of 
this subarray in the final answer will be 13*3=39.
[1]  max of this subarray is 1 so the contribution of this 
subarray in the final answer will be 1*1=1.

So, the answer will be 40 + 39 + 1 = 80.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains two space-separated integers 'n' and 'k', denoting the size of the array and the given integer.

The second line of each test case contains 'n' space-separated integers denoting elements of the array.


Output Format : 
Return the maximum sum of elements after partitioning.


Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.


Sample Input 1:
5 2
1 21 1 5 4


Expected Answer:
56


Output on console:
56


Explanation For Sample Output 1:
We can divide the array into the following subarrays
[1,21] max of this subarray is 21 so the contribution of this subarray in the final answer will be 21*2=42.
[1,5]  max of this subarray is 5 so the contribution of this subarray in the final answer will be 5*2=10.
[4]  max of this subarray is 4 so the contribution of this subarray in the final answer will be 1*4=4.
So, the answer will be 42 + 10 + 4 = 56.


.

Sample Input 2 :
1 1
6


Expected Answer:
6


Output on console:
6


Expected Time Complexity:

Try to solve this in O(n*k).


Constraints:
1 <= 'n' <= 300
0 <= 'arr[i]' <= 10^9
1 <= 'k' <= 'n'

Time limit: 1 sec
Hint

Check for every possible valid way of dividing the array and find the max of all valid ways.

Approaches (3)
Brute Force (Recursion)

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).
Time Complexity

O((2 ^N ) * N), where ‘N’ is the size of the array.

There are 2^N numbers of ways to divide the array and for iterating over all the ‘j’ will take O(N).

Space Complexity

O(N), where ‘N’ is the size of the array.

The recursive stack for the “maxSubarray” function can contain at most the size of the array. Therefore, the overall space complexity will be O(N).

 

Code Solution
(100% EXP penalty)
Partition Array for Maximum Sum
Full screen
Console