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

Other upgrades:

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.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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP