# Pick from both sides?

Stack Overflow Asked by helloworld on December 13, 2020

The problem statement is :
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.

public class Solution {
ArrayList<Integer> c = new ArrayList<>();
ArrayList<Integer> A= new ArrayList<>();
public int solve(ArrayList<Integer> A, int B) {

if (B>A.size()){
int sum=0;
for(int i=0;i<A.size();i++)
sum= sum+A.get(i);
return sum;
}

int max_sum=0;
for(int i=0;i<A.size();i++){
if((max_sum<suffix(A.size()-(B-i))+prefix(i-1)) ){
max_sum=suffix(A.size()-(B-i))+prefix(i-1);
}
}
return max_sum;
}

int prefix_sum=0;
int prefix(int a)   {

for(int p=0;p<a+1;p++){
c=A;
prefix_sum=prefix_sum + c.get(p);
}
return prefix_sum;
}

int suffix_sum=0;
int suffix(int b){
c=A;
for(int q=b;q<c.size();q++){
suffix_sum=suffix_sum+c.get(q);
}
return suffix_sum;
}


}

I am getting runtime error, I have tried to implement the suffix and prefix methods which return the sum from the index[ 0, i] and sum from [i, N-i] respectively, then in the solve function I am trying to find the sum of prefix [a-1] +suffix[N-(b-a)] and find out the maximum sum, the syntax is completely correct, there is something wrong with the logic I assume, please help me find the correct solution by correcting this code instead of providing an alternative method

    package com.array;

import java.util.Arrays;
import java.util.List;

public class PickFromBothSides {

public static void main(String[] args) {
Integer[] arr = { 5, -2, 3, 1, 2 };
System.out.println(solve(Arrays.asList(arr), 3));

}

public static int solve(List<Integer> A, int B) {

int n = A.size();

int result = 0;

for (int i = 0; i < B; i++) {
result += A.get(i);
}

int sum = result;

for (int i = 0; i < B; i++) {
sum -= A.get(B - 1 - i);
sum += A.get(n - 1 - i);

result = Math.max(result, sum);
}

return result;

}
}


Runtime O(n) Space complexity O(1)

Answered by vaquar khan on December 13, 2020

You are declaring int prefix_sum=0; and int suffix_sum=0; as fields, not as local variables of the respective methods.

You are calling suffix(A.size()-(B-i)) so with your example that is 10 - (4 -i) which is 6 + i. You iterate through i being in the range {0, ..., 10} so the value 6 + i will be all the numbers 6 through 16. You cannot index in the array above 9, so you get an exception.

You need to change

for(int i=0;i<A.size();i++){


to

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


because you are trying to ask each iteration "how many numbers are taken from the beginning"? 0, 1, 2, 3 or 4 if B is 4

1. You are calling suffix(A.size()-(B-i))+prefix(i-1)) twice in a row. Call it only once, store it in a variable and reuse.

2. You are calling prefix(i-1) but inside prefix() you are using the parameter a as a + 1. You don't need to subtract one and add one to the same thing

Answered by Hawk on December 13, 2020

## Related Questions

### Trying build a func for multiply which accept any type numbers to work

1  Asked on February 25, 2021 by swiftpunk

### NodeJS – Custom DNS lookup, fallback to ipv4

0  Asked on February 25, 2021 by giyona43

### Hyperledger fabric instantiate timeout because of internet speed, how can I use taobao.org npm image , not official image

0  Asked on February 25, 2021 by user14014310

### How to query the max limit of the data through websocket with python?

0  Asked on February 25, 2021 by user1081544

### Validate input of jTextField using setter java

1  Asked on February 25, 2021 by random

### How to get state variables from one component to another when i’m using history.push?

1  Asked on February 25, 2021 by sai-sagar-seru

### How to make both bits of code run at the same time

1  Asked on February 25, 2021 by atay-hassan

### Parametrized types in Raku, how to use run time values as parameters

4  Asked on February 24, 2021 by jjmerelo

### SSL for pointed domains

1  Asked on February 24, 2021 by userhex

### Warning: Inferring latch for variable ‘w_addra_t’ (in Verilog/SystemVerilog with FOR loop)

2  Asked on February 24, 2021 by france

### Scaling kube-state-metrics in prometheus-operator

1  Asked on February 24, 2021 by bazron

### Encrypt message using RSA on ESP32

0  Asked on February 24, 2021 by daniel-tang

### Counting the occurrences of a substring in a string python

2  Asked on February 24, 2021 by indrajith-ekanayake

### Read data from a pandas DataFrame and create a tree using anytree in python

2  Asked on February 24, 2021 by tendaim

### C# calculations differ between const and variable locals?

1  Asked on February 24, 2021 by ren-van-den-berg

### Dependency Injection: How to get access to the corresponding ProductView that executes the Command?

1  Asked on February 24, 2021 by george-z

### Extracting keys and values from nested Object/Array in Javascript

1  Asked on February 23, 2021 by nitish-kumar

### Python web scraping problems – result different from soruce code

1  Asked on February 23, 2021 by eric-yiu

### I want to change the distance between my image and text and also move all of the items to the left like in image two

1  Asked on February 23, 2021 by lucid

### How do i call API with multiple parameters in android studio

3  Asked on February 23, 2021 by shane