Directi Interview Question Senior Software Development Engineers
Country: India
Interview Type: Phone Interview
It looks to me like a DP problem. Here is my solution.
1> First create sum array, which at each index contains sum of all elements from 'index' to 'index + K' in the given array.
2> Now a recursive function can be written such that it returns sum of max M sub arrays starting from given index. This function iterates over all the overlapping sub arrays starting from index to 'index + K' and recursively calls this function with new non overlapping index and M-1 in each iteration.
3> Use 2D array to store intermediate results that this function returns.
Code looks like this. I have not handled corner conditions
maxSum(index, M){
if(dp[index][M] != null) //Check if we have already calculated it
return dp[index][M];
maxSum = 0;
for(i in index to index+K){
thisMaxSum = sumArray[i] + maxSum(i+K, M-1);
maxSum = thisMaxSum>maxSum ? thisMaxSum : maxSum;
}
dp[index][M] = maxSum; // Store the intermediate result
return maxSum;
}
Can you clarify this question? Isn't it just a matter of finding the MxK largest numbers in the array?
1. it should be subarray , not subsequence of numbers
2. it should be non-overlapping subarray
3. We have to return sum of largest M such subsets..
i didn't get your M * K largest numbers part, what it is ?
To find M subarrays with K elements each to maximize sum(M), you can pick the M*K largest numbers of the array and divide them into M subarrays. The total sum will be the largest possible.
For this, sort the array in descending order and pick the first M*K numbers.
import java.util.*;
public class solution4DP {
public static int maxSum(int[] num, int m, int k){
int sum=0;
List<Integer> sums = new ArrayList<Integer>();
int sum1=0;
for(int i=0; i<k; i++){
sum1+=num[i];
}
sums.add(sum1);
for(int i=k; i<num.length; i++){
int sum2 = sum1-num[i-k]+num[i];
sums.add(sum2);
sum1 = sum2;
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> li = new ArrayList<Integer>();
rec(sums, 0, li, result, m, k);
int sum2=0;
for(int i=0; i<result.size(); i++){
List<Integer> l= result.get(i);
for(int j=0; j<l.size(); j++){
sum2+=l.get(j);
}
sum = Math.max(sum2, sum);
sum2=0;
}
return sum;
}
public static void rec(List<Integer> sums, int n, List<Integer> l, List<List<Integer>> result, int m, int k){
if(l.size()==m){
result.add(l);
return;
}
if(n>sums.size()) return;
for(int i=0; i<k; i++){
if(n+i<sums.size()){
List<Integer> lNew = new ArrayList<Integer>(l);
lNew.add(sums.get(n+i));
rec(sums, n+i+k, lNew, result, m, k);
}else break;
}
rec(sums, n+k, l, result, m, k);
return;
}
public static void main(String[] args){
int[] num = {3,2,100,1};
int m=2; int k=2;
System.out.println(maxSum(num, m, k));
}
}
Here is my solution in c
#include<bits/stdc++.h>
#define ll long long int
#define sd1(a) scanf("%d",&a)
#define sd2(a,b) scanf("%d %d",&a,&b)
#define sd3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define slld1(a) scanf("%lld",&a)
#define slld2(a,b) scanf("%lld %lld",&a,&b)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loope(i,a,b) for(int i=a;i<=b;i++)
#define loopd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int main()
{
int n,m,k,i,j;
sd3(n,m,k);
int a[n];
int dp[n][k];
int sum[n];
for(i=0;i<n;i++)
sd1(a[i]);
int s=0;
for(i=0;i<k-1;i++)
{
sum[i]=0;
s+=a[i];
}
sum[i]=s+a[k-1];
for(i=k;i<n;i++)
{
sum[i]=sum[i-1]-a[i-k]+a[i];
}
/*for(i=0;i<n;i++)
printf("%d ",sum[i]);
cout<<endl;*/
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
if(i==0 || j==0 || i<(j*k-1))
dp[i][j]=0;
else
dp[i][j]=max(dp[i-1][j],dp[i-(k-1)][j-1]+sum[i]);
printf("%d ",dp[i][j]);
}
//cout<<endl;
}
printf("%d\n",dp[n-1][k-1]);
}
#include<bits/stdc++.h>
#define ll long long int
#define sd1(a) scanf("%d",&a)
#define sd2(a,b) scanf("%d %d",&a,&b)
#define sd3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define slld1(a) scanf("%lld",&a)
#define slld2(a,b) scanf("%lld %lld",&a,&b)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loope(i,a,b) for(int i=a;i<=b;i++)
#define loopd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int main()
{
int n,m,k,i,j;
sd3(n,m,k);
int a[n];
int dp[n][k];
int sum[n];
for(i=0;i<n;i++)
sd1(a[i]);
int s=0;
for(i=0;i<k-1;i++)
{
sum[i]=0;
s+=a[i];
}
sum[i]=s+a[k-1];
for(i=k;i<n;i++)
{
sum[i]=sum[i-1]-a[i-k]+a[i];
}
/*for(i=0;i<n;i++)
printf("%d ",sum[i]);
cout<<endl;*/
for(i=0;i<n;i++)
{
for(j=0;j<k;j++)
{
if(i==0 || j==0 || i<(j*k-1))
dp[i][j]=0;
else
dp[i][j]=max(dp[i-1][j],dp[i-(k-1)][j-1]+sum[i]);
printf("%d ",dp[i][j]);
}
//cout<<endl;
}
printf("%d\n",dp[n-1][k-1]);
}
This should work fine, If you find something wrong with this please let me know.
import java.util.*;
import java.lang.*;
public class solution{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
int n,m,k;
n=sc.nextInt();
m=sc.nextInt();
k=sc.nextInt();
int arr[]=new int[n];
for (int i=0;i<n ;i++ ) {
arr[i]=sc.nextInt();
}
int subm[]=new int[n/k];
int l;
for(l=0;l<n/k;l++){
subm[l]=0;
}
l=0;
for(int i=0;i<=n-k;i=i+k){
for(int j=i;j<i+k;j++){
subm[l]=subm[l]+arr[j];
}
l++;
}
System.out.println("OUTPUT");
for(l=0;l<n/k;l++){
System.out.println(subm[l]);
}
int ans=0;
for(int i=0;i<m;i++){
ans=ans+max(subm);
subm[Arrays.binarySearch(subm,max(subm))]=0;
}
System.out.println("ANS="+ans);
}
public static int max(int a[]){
int m;
m=a[0];
for (int i=1;i<a.length ;i++ ) {
if(a[i]>m){
m=a[i];
}
}
return m;
}
}
import java.util.*;
import java.lang.*;
public class solution{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
int n,m,k;
n=sc.nextInt();
m=sc.nextInt();
k=sc.nextInt();
int arr[]=new int[n];
for (int i=0;i<n ;i++ ) {
arr[i]=sc.nextInt();
}
int subm[]=new int[n/k];
int l;
for(l=0;l<n/k;l++){
subm[l]=0;
}
l=0;
for(int i=0;i<=n-k;i=i+k){
for(int j=i;j<i+k;j++){
subm[l]=subm[l]+arr[j];
}
l++;
}
System.out.println("OUTPUT");
for(l=0;l<n/k;l++){
System.out.println(subm[l]);
}
int ans=0;
for(int i=0;i<m;i++){
ans=ans+max(subm);
subm[Arrays.binarySearch(subm,max(subm))]=0;
}
System.out.println("ANS="+ans);
}
public static int max(int a[]){
int m;
m=a[0];
for (int i=1;i<a.length ;i++ ) {
if(a[i]>m){
m=a[i];
}
}
return m;
}
}
Read the code comments to understand it.
A very basic recursion approach is used here.
#include<bits/stdc++.h>
using namespace std;
int solve(int presum[],int m,int sz,int k,int start){
if(m==0)
return 0;
if(start>sz-1)
return 0;
int mx =0;
//if you are including subarray of size k
int tmpmax = presum[start]+solve(presum,m-1,sz,k,start+k);
//if you are excluding the element and seaching in all next possible subarrays
int tp = solve(presum,m,sz,k,start+1);
//return the max
return max(tmpmax,tp);
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int m,k;
cin>>m>>k;
int presum[n+1-k]={0};
//store the sum of array from index i to index i+k in presum array at index i of it.
for(int i=0;i<=n-k;i++){
for(int j=i;j<i+k;j++){
presum[i]+=arr[j];
}
}
//the resulting presum array will have a size = n+1-k
int ans = solve(presum,m,n+1-k,k,0);
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int solve(int presum[],int m,int sz,int k,int start){
if(m==0)
return 0;
if(start>sz-1)
return 0;
int mx =0;
//if you are including subarray of size k
int tmpmax = presum[start]+solve(presum,m-1,sz,k,start+k);
//if you are excluding the element and seaching in all next possible subarrays
int tp = solve(presum,m,sz,k,start+1);
//return the max
return max(tmpmax,tp);
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
int m,k;
cin>>m>>k;
int presum[n+1-k]={0};
//store the sum of array from index i to index i+k in presum array at index i of it.
for(int i=0;i<=n-k;i++){
for(int j=i;j<i+k;j++){
presum[i]+=arr[j];
}
}
//the resulting presum array will have a size = n+1-k
int ans = solve(presum,m,n+1-k,k,0);
cout<<ans;
return 0;
}
Calculate sum[i]=sum of K consecutive numbers ending at index i
- prateekjjw001 June 08, 2015dp[i,j] = max sum possible in [1...i] and j number of sub arrays;
dp[i,j]=max(dp[i-1,j],dp[i-k,j-1]+sum[i])
You have two options, either to include the subarray ending at index i or not to include it.
answer=dp[n,k]
Complexity O(NK)