Posts Pick from both sides (Interviewbit)
Post
Cancel

Pick from both sides (Interviewbit)

PROBLEM DESCRIPTION

Given an integer array A of size N. You have to pick exactly B elements from either left or right end of the array A to get the maximum sum. Find and return this maximum possible sum.

interviewbit

SOLUTION

APPROACH 1 (Dynamics Programming | Out of Memory)

Note that this solution was not accepted (failed the hard test due to OOM) so it may not be accurate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {

    public int solve(int[] A, int B) {

        int n = A.length;

        // i -> elements from left which can be from 0 to n-1
        // j -> elements from right which can be from n-1 to 0
        // so we will need a dp of size n x n
        int[][] dp = new int[n][n];

        //init dp with -1
        for(int i=0; i<n; i++){
            Arrays.fill(dp[i], -1);
        }

        return helper(A, B, 0, A.length-1, dp);
    }

    public int helper(int[] A, int B, int i, int j, int[][] dp){

        // if we have chosen all B elements already, return 0 sum
        if(B == 0) return 0;

        //if the max sum was not calculated for current (i, j) state, calculate & store it
        if(dp[i][j] == -1){

            //max sum, if we select the left element then using recursion for the sub-problem
            int chooseLeft = A[i] + helper(A, B-1, i+1, j, dp);

            //max sum if we select the right element then using recursion for the sub-problem
            int chooseRight = A[j] + helper(A, B-1, i, j-1, dp);

            //take the max from the above choices
            dp[i][j] = Math.max(chooseLeft, chooseRight);

        }

        return dp[i][j];

    }

}

APPROACH 2 (Using Prefix/Suffix Array) - Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {

    public int solve(int[] A, int B) {

        int maxSum = Integer.MIN_VALUE;

        int n = A.length;

        //prefix array
        int[] pfl = new int[n];
        pfl[0] = A[0];
        for(int i=1; i<n; i++) pfl[i] = A[i] + pfl[i-1];

        //suffix array
        int[] pfr = new int[n];
        pfr[n-1] = A[n-1];
        for(int i=n-2; i>=0; i--) pfr[i] = A[i] + pfr[i+1];

        for(int i=0; i<=B; i++){

            int l = i;  //choose i elements from the left
            int r = B-i;//choose the rest (B-i) elements from the right

            int leftSum = 0;
            int rightSum = 0;

            if(l > 0) leftSum = pfl[l-1];
            if(r > 0) rightSum = pfr[n-r];

            // update max, if this combination gives a higher sum
            maxSum = Math.max(maxSum, leftSum + rightSum);

        }

        return maxSum;

    }
}
This post is licensed under CC BY 4.0 by the author.