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.
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.
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.
Return the maximum sum of elements after partitioning.
You do not need to print anything, it has already been taken care of. Just implement the given function.
5 2
1 21 1 5 4
56
56
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.
.
1 1
6
6
6
Try to solve this in O(n*k).
1 <= 'n' <= 300
0 <= 'arr[i]' <= 10^9
1 <= 'k' <= 'n'
Time limit: 1 sec
Check for every possible valid way of dividing the array and find the max of all valid ways.
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:
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).
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).
All tags
Sort by
Interview problems
C++ Solution || TABULATION
TABULATION :-
int maximumSubarray(vector<int> &arr, int k){
int n = arr.size();
vector<int> dp(n+1,0);
for(int i = n-1 ; i>= 0 ; i--){
int MaxSum = INT_MIN;
int tempMaxi = INT_MIN;
for(int j = i ; j<min(i+k,n) ; j++){
int tempMaxi = max(tempMaxi,arr[j]);
int maxi = tempMaxi*(j-i+1) + dp[j+1];
MaxSum = max(MaxSum,maxi);
}
dp[i] = MaxSum;
}
return dp[0];
}Interview problems
c++ || solution
int maximumSubarray(vector<int> &arr, int k){
int n = arr.size();
vector<int> dp(n+1,0);
for(int i=n-1; i>=0; i--){
int res = 0,maxNum=INT_MIN;
for(int ind=i; ind< min(i+k,n); ind++){
maxNum = max(maxNum,arr[ind]);
res = max(res,(ind-i+1) * maxNum + dp[ind+1]);
}
dp[i] = res;
}
return dp[0];
}
Interview problems
C++ || Memoization solution
#include<bits/stdc++.h>
int recursion(int idx, int k, int n, vector<int> &arr, vector<int> &dp){
if(idx == n){
return 0;
}
if(dp[idx] != -1){
return dp[idx];
}
int len = 0;
int maxVal = INT_MIN;
int maxSum = INT_MIN;
for(int j=idx; j<min(idx+k, n); j++){
len++;
maxVal = max(maxVal, arr[j]);
int sum = maxVal*len + recursion(j+1, k, n, arr, dp);
maxSum = max(sum, maxSum);
}
return dp[idx] = maxSum;
}
int maximumSubarray(vector<int> &arr, int k){
int n = arr.size();
vector<int> dp(n, -1);
return recursion(0, k, n, arr, dp);
}
Interview problems
memoization|cpp
# include<bits/stdc++.h>
bool isValid(int i,int j,int k){
if(j-i+1 <= k){
return 1;
}
return 0;
}
int func(int i,int j,int k,vector<int>&arr, vector<vector<int>>&dp){
if(i>j)return 0;
if(isValid(i,j,k)){
int maxele=0;
for(int it=i;it<=j;it++){
maxele= max(arr[it],maxele);
}
return (j-i+1)*maxele;
}
if(dp[i][j]!=-1)return dp[i][j];
int maxi=-10e7;
for(int x=0;x<k;x++){
int ans = func(i,i+x,k,arr,dp)+func(i+x+1,j,k,arr,dp);
maxi=max(ans,maxi);
}
return dp[i][j]= maxi;
}
int maximumSubarray(vector<int> &arr, int k){
// Write your code here.
int n =arr.size();
vector<vector<int>>dp(n,vector<int>(n,-1));
return func(0,n-1,k,arr,dp);
}
Interview problems
from recursion to tabulation best space complexity Partition Array for Maximum Sum
#include <bits/stdc++.h>
typedef long long ll;
// ll solve(int i, int k, vector<int>& nums, vector<ll>& dp) {
// int n = nums.size();
// if (i == n) return 0;
// if (dp[i] != -1) return dp[i];
// int len = 0;
// ll maxi = -1e9, maxans = -1e9;
// for (int idx = i; idx < min(n, i + k); idx++) {
// len++;
// maxi = max(maxi, (ll)nums[idx]);
// ll sum = len * maxi + solve(idx + 1, k, nums, dp);
// maxans = max(maxans, sum);
// }
// return dp[i] = maxans;
// }
// int maximumSubarray(vector<int> &nums, int k)
// {
// int n=nums.size();
// vector<ll>dp(n,-1);
// return solve(0,k,nums,dp);
// }
int maximumSubarray(vector<int>& arr, int k) {
int n = arr.size();
vector<ll> dp(n+1,0);
for(int i=n-1; i>=0; i--)
{
int maxi=-1e9,maxans=-1e9;
ll len=0;
for(int j=i; j<min(n,i+k); j++)
{
len++;
maxi=max(maxi,arr[j]);
int sum=len*maxi+dp[j+1];
maxans=max(sum,maxans);
}
dp[i]=maxans;
}
return dp[0];
}Interview problems
mem + tab solution
#include <bits/stdc++.h>
int solve(int index, int k , vector<int>&num,vector<int>&dp){
int n = num.size();
if(index==n)
return 0;
int maxi=INT_MIN;
int maxians=INT_MIN;
int len=0;
if(dp[index]!=-1)
return dp[index];
for(int j = index; j < min(n, index+k); j++){
len++;
maxi=max(maxi, num[j]);
int ans = len*maxi + solve(j+1, k , num,dp);
maxians=max(maxians, ans);
}
return dp[index]=maxians;
}
int tab(vector<int>&num, int k){
int n = num.size();
vector<int>dp(n+1,0);
dp[n]=0;
for(int index = n-1; index >=0 ; index--){
int maxi=INT_MIN;
int maxians=INT_MIN;
int len=0;
for(int j = index; j < min(n, index+k); j++){
len++;
maxi=max(maxi, num[j]);
int ans = len*maxi + dp[j+1];
maxians=max(maxians, ans);
}
dp[index]=maxians;
}
return dp[0];
}
int maximumSubarray(vector<int> &num, int k)
{
// Write your code here.
// int n = num.size();
// vector<int>dp(n+1, -1);
// return solve(0, k , num, dp);
return tab(num,k);
}
Interview problems
Python easy solution using python.
def f(idx,arr,k,dp,n):
if idx==len(arr) or k<0:return 0
if dp[idx]!=-1:return dp[idx]
Max=float("-inf")
Maxsum=float("-inf")
for i in range(idx,min(idx+k,n)):
Max=max(Max,arr[i])
Sum=(i-idx+1)*Max+f(i+1,arr,k,dp,n)
Maxsum=max(Maxsum,Sum)
dp[idx]=Maxsum
return dp[idx]
def maximumSubarray(arr: List[int], k: int) -> int:
n=len(arr)
dp=[-1]*n
return f(0,arr,k,dp,n)Please Upvote!!!
Interview problems
Misleading statement
The statement says that we have to divide the array into subarrays such that each element is a part of exactly one subarray. But see the first example test case. The way they have solved the test case doesn't follow the first rule because they have taken 1 in two different subarrays. They have ignored the first rule. So while solving keep that point in mind. There is no need to keep all instances of an element in a single subarray.
Easy C++ solution using memoization
#include <bits/stdc++.h>
int helper(vector<int>&num,int k,int index,vector<vector<int>>&dp) {
if(index==num.size()) {
return dp[index][k]=0;
}
if(dp[index][k]!=-1) {
return dp[index][k];
}
int element=INT_MIN,ans=INT_MIN;
for(int i=index;i<min((int)num.size(),index+k);i++) {
element=max(element,num[i]);
if(dp[i+1][k]==-1) {
dp[i+1][k]=helper(num,k,i+1,dp);
}
ans=max(ans,((i-index+1)*element)+dp[i+1][k]);
}
return dp[index][k]=ans;
}
int maximumSubarray(vector<int> &num, int k) {
vector<vector<int>>dp(num.size()+1,vector<int>(k+1,-1));
return helper(num,k,0,dp);
}Interview problems
Python Solution
from os import *
from sys import *
from collections import *
from math import *
from typing import List
def maximumSubarray(num: List[int], k: int) -> int:
n = len(num)
def solve(i):
if(i==n):
return 0
if(memo[i] != (-1)):
return memo[i]
ans,maxi = 0,0
for j in range(i,min(i+k,n)):
maxi = max(maxi,num[j])
steps = ((j-i+1)*maxi)+solve(j+1)
ans = max(steps,ans)
memo[i] = ans
return memo[i]
memo = [-1 for i in range(n)]
return solve(0)Interview problems
Discussion thread on Interview Problem | Partition Array for Maximum Sum
Hey everyone, creating this thread to discuss the interview problem - Partition Array for Maximum Sum.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Partition Array for Maximum Sum
