Pick from both sides

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

NOTE: Suppose B = 4 and array A contains 10 elements then

• You can pick first four elements or can pick last four elements or can pick 1 from front and 3 from back etc. you need to return the maximum possible sum of elements you can pick.

Solution:

Take the inputs in whatever way you want. For this example, I will be using C++.

int n;
scanf("%d", &n);
int nums[n];
for( int i=0; i<n; i++ )
    scanf("%d", &nums[i]);
int k;
scanf("%d", &k);

Create an array of the cycle of elements which can be inside the subarray.

vector<int> cycle;

For this we can first take the first k elements from the left in the direction of right to left.

for( int i=k-1; i>=0; i-- )
    cycle.push_back( nums[i] );

Next, we’ll take the k elements from the left from right to left.

for( int i=n-1; i>= n-1-k; i-- )
    cycle.push_back( nums[i] );

Find the initial maxSum by adding the first k elements of the cycle.

int maxSum = 0;
for( int i=0; i<k; i++ )
    maxSum += cycle[i];

Use two pointer method to traverse to the end of the array and find the max sum.

int sum = maxSum;
int front = 0;
int back = k;
while( back < cycle.size() ) {
    sum = sum - cycle[front] + cycle[back];
    maxSum = max( maxSum, sum );
    front++;
    back++;
}

Now the answer will be stored in maxSum which you can later use for the purpose you want.

Full Code:

int maxSumBothSides( vector<int> &nums, int k ) {
    vector<int> cycle;
    for( int i=k-1; i>=0; i-- )
        cycle.push_back( nums[i] );
    for( int i=n-1; i>=0 && i>n-k-1; i-- )
        cycle.push_back( nums[i] );
    int maxSum = 0;
    for( int i=0; i<k; i++ )
        maxSum += cycle[i];
    int cycleSize = cycle.size(), sum = maxSum;
    int front = 0, back = k;
    
    while( back < cycleSize ) {
        sum = sum - cycle[front] + cycle[back];
        maxSum = max( sum, maxSum );
        front++;
        back++;
    }
    return maxSum;
}