stays the same - you just change the second and third arguments specifying differnt protions

so when you both arguments second and third becomes equal then you return this elemnt of the array or zero if it is negative

Solved

Posted on 2011-10-03

There is a simple program in my textbook that I pasted below. There is a method in the program that takes an array, divides it evenly into two arrays, and recursively passes each half-array back into the method until it reaches the base case. Then, the program figures out what the biggest subsequence is in each half-array, considering that the subsequence MUST touch the center divider. In other words, anything this program sums up must include either -2 or -1 from myArray below.

For-yan, or anyone, can you explain to me what is happening to the half-arrays in line 24 and 25? Specifically, I want to know how the recursion stops and what the arrays look like when the recursion is done.**Please do not make more than 1 post if possible**, and don't include any information that's not related to my question about lines 24 and 25. Thanks very much!

For-yan, or anyone, can you explain to me what is happening to the half-arrays in line 24 and 25? Specifically, I want to know how the recursion stops and what the arrays look like when the recursion is done.

```
public class SplitSubsequence {
public static void main(String[] args) {
int[] myArray = {4,-3,5,-2,-1,2,6,-2};
System.out.println(maxSumRec(myArray, 0, myArray.length -1));
}
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec( int [ ] a, int left, int right )
{
int maxLeftBorderSum = 0, maxRightBorderSum = 0;
int leftBorderSum = 0, rightBorderSum = 0;
int center = ( left + right ) / 2;
if( left == right ) // Base case
return a[ left ] > 0 ? a[ left ] : 0;
int maxLeftSum = maxSumRec( a, left, center );
int maxRightSum = maxSumRec( a, center + 1, right );
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
return maxLeftSum + maxRightSum;
}
}
```

30 Comments

stays the same - you just change the second and third arguments specifying differnt protions

so when you both arguments second and third becomes equal then you return this elemnt of the array or zero if it is negative

The result of this program is 11 if you make the correction on line 41. Can you type for me the numbers that were added out of {4,-3,5,-2,-1,2,6,-2} BEFORE arriving at the answer of 11? In other words, I want to know in chronological order what the program is adding, step by step arithmetic, before getting the final answer of (4+(-3)+5+(-2)) + (-1+2+6) = 11

So execute the code where I added some printout (or look at its output at the bottom)

and you'll see that array on all iterations remains the same, so neither at lines 24,25 or at any other lines

nothing is being changed in the array:

```
public class SplitSubsequence {
static int count = 0;
public static void main(String[] args) {
int[] myArray = {4,-3,5,-2,-1,2,6,-2};
System.out.println(maxSumRec(myArray, 0, myArray.length -1));
}
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec( int [ ] a, int left, int right )
{
System.out.print(" printing arry for the " + count + " th time: ");
count++;
for (int ii: a){
System.out.print(ii + ",");
}
System.out.println(" ");
int maxLeftBorderSum = 0, maxRightBorderSum = 0;
int leftBorderSum = 0, rightBorderSum = 0;
int center = ( left + right ) / 2;
if( left == right ) // Base case
return a[ left ] > 0 ? a[ left ] : 0;
int maxLeftSum = maxSumRec( a, left, center );
int maxRightSum = maxSumRec( a, center + 1, right );
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
return maxLeftSum + maxRightSum;
}
}
```

```
printing arry for the 0 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 1 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 2 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 3 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 4 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 5 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 6 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 7 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 8 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 9 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 10 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 11 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 12 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 13 th time: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 14 th time: 4,-3,5,-2,-1,2,6,-2,
17
```

```
public class SplitSubsequence {
public static void main(String[] args) {
int[] myArray = {4,-3,5,-2,-1,2,6,-2};
System.out.println(maxSumRec(myArray, 0, myArray.length -1));
}
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec( int [ ] a, int left, int right )
{
int maxLeftBorderSum = 0, maxRightBorderSum = 0;
int leftBorderSum = 0, rightBorderSum = 0;
int center = ( left + right ) / 2;
if( left == right ) // Base case
return a[ left ] > 0 ? a[ left ] : 0;
int maxLeftSum = maxSumRec( a, left, center );
int maxRightSum = maxSumRec( a, center + 1, right );
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
return maxLeftBorderSum + maxRightBorderSum;
}
}
```

```
public class SplitSubsequence {
static int count = 0;
public static void main(String[] args) {
int[] myArray = {4,-3,5,-2,-1,2,6,-2};
System.out.println(maxSumRec(myArray, 0, myArray.length -1, "first call"));
}
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec( int [ ] a, int left, int right, String which )
{
System.out.print(" printing arry for the " + count + " th time " + which + ": ");
count++;
for (int ii: a){
System.out.print(ii + ",");
}
System.out.println(" ");
int maxLeftBorderSum = 0, maxRightBorderSum = 0;
int leftBorderSum = 0, rightBorderSum = 0;
int center = ( left + right ) / 2;
if( left == right ) {
System.out.println(" returning from base case " + which + " " + a[left] ); // Base case
return a[ left ] > 0 ? a[ left ] : 0;
}
int maxLeftSum = maxSumRec( a, left, center, "first call" );
int maxRightSum = maxSumRec( a, center + 1, right, "second call" );
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
System.out.println(" returning from the bottom " + which + " " + (maxLeftBorderSum + maxRightBorderSum));
return maxLeftBorderSum + maxRightBorderSum;
}
}
```

Output:

```
printing arry for the 0 th time first call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 1 th time first call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 2 th time first call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 3 th time first call: 4,-3,5,-2,-1,2,6,-2,
returning from base case first call 4
printing arry for the 4 th time second call: 4,-3,5,-2,-1,2,6,-2,
returning from base case second call -3
returning from the bottom first call 4
printing arry for the 5 th time second call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 6 th time first call: 4,-3,5,-2,-1,2,6,-2,
returning from base case first call 5
printing arry for the 7 th time second call: 4,-3,5,-2,-1,2,6,-2,
returning from base case second call -2
returning from the bottom second call 5
returning from the bottom first call 6
printing arry for the 8 th time second call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 9 th time first call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 10 th time first call: 4,-3,5,-2,-1,2,6,-2,
returning from base case first call -1
printing arry for the 11 th time second call: 4,-3,5,-2,-1,2,6,-2,
returning from base case second call 2
returning from the bottom first call 2
printing arry for the 12 th time second call: 4,-3,5,-2,-1,2,6,-2,
printing arry for the 13 th time first call: 4,-3,5,-2,-1,2,6,-2,
returning from base case first call 6
printing arry for the 14 th time second call: 4,-3,5,-2,-1,2,6,-2,
returning from base case second call -2
returning from the bottom second call 6
returning from the bottom second call 8
returning from the bottom first call 11
11
```

go to this link:

http://cs.unomaha.edu/~sta

and on page 2 in boxes labeled "Algorithm 3" they give detailed

explanation of how this thing works

and you know what - the code you posted is not correct.

This is the correct one:

Looke here:

http://www.java-tips.org/j

```
private static int maxSumRec( int [ ] a, int left, int right )
{
int maxLeftBorderSum = 0, maxRightBorderSum = 0;
int leftBorderSum = 0, rightBorderSum = 0;
int center = ( left + right ) / 2;
if( left == right ) // Base case
return a[ left ] > 0 ? a[ left ] : 0;
int maxLeftSum = maxSumRec( a, left, center );
int maxRightSum = maxSumRec( a, center + 1, right );
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
return max3( maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum );
}
/**
* Return maximum of three integers.
*/
private static int max3( int a, int b, int c )
{
return a > b ? a > c ? a : c : b > c ? b : c;
}
```

- indeed you split into two parts and (forget about one leements first)

and apply the same function to left part, to right part and check for the common elment ioincrease

whchever one becmes gretetr that will be the maximum

and you split this way all the time until one of your parts becomes one element and then the function upon this one element will be this element itself and then

like in all recursions you actually go back through bigger elements

```
public class test {
public static void main(String[] args) {
int[] myArray = {4,-2,5,-2,-1,-2};
System.out.println(maxSumRec(myArray, 0, myArray.length -1));
}
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec( int [ ] a, int left, int right )
{
if( left == right ) // Base case
return a[ left ] > 0 ? a[ left ] : 0;
int center = ( left + right ) / 2;
int maxLeftSum = maxSumRec( a, left, center );
int maxRightSum = maxSumRec( a, center + 1, right );
int maxLeftBorderSum = 0, leftBorderSum = 0;
for( int i = center; i >= left; i-- )
{
leftBorderSum += a[ i ];
if( leftBorderSum > maxLeftBorderSum )
maxLeftBorderSum = leftBorderSum;
}
int maxRightBorderSum = 0, rightBorderSum = 0;
for( int i = center + 1; i <= right; i++ )
{
rightBorderSum += a[ i ];
if( rightBorderSum > maxRightBorderSum )
maxRightBorderSum = rightBorderSum;
}
return maxLeftBorderSum + maxRightBorderSum;
}
}
```

sequence - I'm sure you can invent the sequrnce when that code would have been be wrong.

And yes, you are right - the stopping point of recusrsion is when you get to one element, as this has obvious solution for maxRecSum() function

but you never compare eight sets of 1, you get to these ones, and from them

go backwards determining maxSumRec for bigger and bigger chunks

In fact you enter this method as a whole 15 times, but I could not have counted it without computer

is still incorrect - in fact it does not use the values of

maxLeftSum and maxRightSum (only assigns to them and never uses them) which is wrong

the last return line should be

return max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum, maxRightSum );

and max3 is a simple function finding the biggest of three numbers

with this, the whole algorithm becomes much more understandable

as made up of the functions on smaller sets and theese smaller sets on even smaller sets until

you finally come to such small arguments when the function is obvious and then

you go back recalculatiing functions on bigger chunks from those form smaller chunks

and eventually come back to your original set

In my most recent example with the array {4,-2, 5,-2,-1,-2}, what is value of maxLeftSum and maxRightSum at the end of the program?

Absolutely correct.

I was sitting and trying to make any sense of it, until it occurred to me to browse internet and I found there this difference.

The main point of recursion is reduction of function on bigger argument to function(s) on smaller arguments - and tht's waht we see in this formula:

return max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum, maxRightSum );

>In my most recent example with the array {4,-2, 5,-2,-1,-2}, what is value of maxLeftSum and maxRightSum at the end of the program?

On the last stage for that array say we'll split into

4,-2,5 and -2,-1,-2

maxLeftBorderSum = 5

maxRightBorderSum = 0

so maxLeftBorderSum + maxRightBorderSum = 5

maxLeftSum will be 7

maxRightSum will be 0

so max3(maxLeftBorderSum + maxRightBorderSum, maxLeftSum, maxRightSum ) = 7

so we may have

4

-2

5

4,-2

-2,5

4,-2,5

I just summed them up and got the last one the biggest

Computer will of course split it again in two - sya 4,-2 and 5 and in this case

it will find that the sum "across common element" - will be the biggest

if( left == right )

return a[ left ] > 0 ? a[ left ] : 0;

int maxLeftSum = maxSumRec( a, left, center );

int maxRightSum = maxSumRec( a, center + 1, right );

-1,2,4

we split it

to

-1,2 and 4

so whan we calculate rightsum - we have base case return and 4

when left sum we split

-1 and 2

out of this we have 2

so now we are back

with

2 and 4

both have base case return

but across-center wins with 6

and then we compare with the left three

we're looking at

we split the left side to

we split those two into

Now

or compares three - left , right and across

so

we split

-1,2 and 4,4

then calculatiing on the left we split

-1 and 2 - result 2

on the right we split

4 and 4

across the center wins - 8

now we have

2 and 8

across the ccenter wins 10

so 10 is the result of the function on the left side

Or better put, how many times does the first half of the array (-1, 2, 4, 4) cause the for loops in the program to be used? I DO NOT want to know how many times the for loops

{-1, 2, 4, 4} interacts with the for loops

(-1, 2) and (4, 4) interact with the for loops

(-1) and (2) and (4) and (4) interact with the for loops as single numbers

OK, let;s start from two numbers in array (4,4):

maxSumRec(our arrya is 4,4)

so we don't exit on the base case as we have still two numbers

but then we split and

we got to first call with just one number array 4 and we return from this first call 4 on the base case

then we go to the lft-side call part also with one number and we return opn the base case with 4

and then we go into your loops 25-38 with leftsum 4, and rightsum 4

and we determine that acrosssum - 8 will be bigger - so 8 will be the result

so in your words it will mean that if we start frfom (4,4) we just go through these lines only once

Title | # Comments | Views | Activity |
---|---|---|---|

FizzBuzz challenge | 9 | 65 | |

JVM encoding. How to change encoding. | 27 | 55 | |

Exception after setting jdbc session management | 2 | 17 | |

@SBGen Method | 3 | 17 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**17** Experts available now in Live!