Solved

Posted on 2011-10-02

My textbook shows the code below when discussing a maximum subsequence sum problem, but I don't understand what it is trying to achieve. I entered in some numbers myself into myArray and it seems like it is just adding up all the elements of the array and returning the sum. Why is it using three loops to do this? Seems so excessive.

```
public class test {
public static void main(String[] args) {
int[] myArray = {1,3,2,6,9};
System.out.println(maxSubSum1(myArray));
}
public static int maxSubSum1(int[] a){
int maxSum = 0;
for(int i = 0; i < a.length; i++){
for(int j = i; j < a.length; j++){
int thisSum = 0;
for(int k = i; k <= j; k++)
thisSum += a[k];
if(thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
}
```

50 Comments

in you use this array:

```
int[] myArray = {1,3,-6,3,9};
```

The result will be 12 as the sum of 3 +9 last two elememts

calculate sum of all numbers between and then detrmine the maximum of the sum

not too big arraays it is not important

with one element equal to their sum

like in my example above change that initial array to

4,-6,12

- this will have less elements and it will be faster in case of long arrays

and then you'll have alternating + and - elements - it again can be somehow sped up, rather than doing three loops.

But again that is worth doing when this is a bottleneck,

otherwise the straightforward solution above is fine

I think I understand what the first loop does, it just repeats the code a.length times, which in my code above is 5 times.

I think I understand what the third loop does, it just gets expressed once each time and adds a[k] to thisSum.

I have no idea what the point of the second loop is. What is it doing, in the most basic basic terms please?

You'll use one for loop to select all cases for the beginning index

You'll use the next for loop to selec the ending index (this is the second loop)

The only small additional point is that seconnd loop you'll start from the selected first index, as ending index should always be bigger than the starting index

in between and add then to determinr the sum and then compare with the previous value of maximum sum

and assign the new value if it is bigger

determined by two index values - the starting index and the ending index - and to select two indexs you need to have two loops

1+2+3+4+(-5) =

2+3+4+(-5) =

3+4+(-5) =

4+(-5) =

(-5) =

It seems to me that the maximum sum is 5, so why is my program resulting in 10?

The forst loop goese through indexes

0,1,2,3,4,5

when you esatblaish fisrt index say 0

then with i = 0, second loop will go through 0,1,2,3,4,5 - on each od these

second loop steps you end up with two indexes

say

i = 0, j =3

then for these two fixed indexs your third lopop

will iterate form index 0 to index 3 and make a summation

then you'll compare the sum with current maximum and asiign it to cuyrent maximu if ithe sum is bigger

Each subsequrnce is defined by beginning index and ending index

beginning index is a number between 0 and <=4 and ending index is a number between 0 and <=4

inorder to go through all subsequebnces you should go through all possible pairs of beginning and ending indexs -

this is what these first two loops are doing - they are just enumerating all possible pairs of beginning and ending indexs

Once you have fixed on one particula pair - then the third loop

sums up all the elments of the array between the starting index and the ending index to finfd the subsequence sum

And then as you alwyas determine maximum you just compare with the current maximum

Please assume that we have an array called myArray with five elements, and here are the elements: {1,2,3,4,-5}. Notice how the last number in that set of five numbers is negative. Now, without explaining any computer code, I want to know what arithmetic the program is performing on the five numbers that I just mentioned. Can you write down for me everything the computer adds like I did below, and then type what it returns? Again, I don't want to understand anything about the program except the step-by-step arithmetic that is going on.

2+3+4+(-5) = 4

3+4+(-5) = 2

4+(-5) = -1

(-5) = -5

Return 5

Now computer makes much more than what you wriote - if you do just that waht you showed, then you'll not catch the real maximum subsequence which is in this case

1+2+3+4 = 10

that's why you need to gro through allpossible pairs of starting and ending indexes to go through all possible subsequences

Array is:

1,2,3,-4

combinations:

1

1,2

1,2,3

1,2,3,-4

2,

2,3

2,3,-4

3

3,-4

1

1+2

1+2+3

1+2+3+(-4)

2

2+3

2+3+(-4)

3

3+(-4)

1

1,2

1,2,3

1,2,3,-4

2,

2,3

2,3,-4

3

3,-4

-4

so maximum will be 1+2+3 = 6

So to gete the sum of each subsequence yes you need to sum up all of them

So if you use you method you'll cover only part of all possible subsequences and will miss the biggest sum

```
public static int maxSubSum1(int[] a){
int maxSum = 0;
int thisSum = 0;
for(int i = 0; i < a.length; i++){
for(int j = i; j < a.length; j++){
thisSum += a[j];
if(thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
```

Look in the real method they assign thisSum = 0;

before staring cacluclating subsequence

and in your code it accumlate and accumaulate and accuymlutae the sum

beyond any susbequence value

Please, read my post

ID:36900850

and explain what poinnt you don't understand.

```
public class Test {
public static void main(String[] args) {
int[] myArray = {-1,2,3,-4};
System.out.println(maxSubSum1(myArray));
}
public static int maxSubSum1(int[] a){
int maxSum = 0;
int thisSum = 0;
for(int i = 0; i < a.length; i++){
for(int j = i; j < a.length; j++){
thisSum += a[j];
if(thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
}
```

(it returns 7 - an there is no subsequence with 7 -

maximum is 1+2+3 = 6

Look at the code - to calclualte subsequernce sum you need to start from zero

for each subsequence - here you juts kee summing

elements all the time it cannot be right

You just found the array where that was the coincidence - that does not mean that the prfogram works right.

Once again - try to read the explanation and point out what it is that you don't udnesratnd

)

```
public class Test {
public static void main(String[] args) {
int[] myArray = {1,2,3,-4};
System.out.println(maxSubSum1(myArray));
}
public static int maxSubSum1(int[] a){
int maxSum = 0;
int thisSum = 0;
for(int i = 0; i < a.length; i++){
for(int j = i; j < a.length; j++){
thisSum += a[j];
if(thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
}
```

Output:

```
7
```

```
public class test {
public static void main(String[] args) {
int[] myArray = {-1,2,3,-4,6};
System.out.println(maxSubSum1(myArray));
}
public static int maxSubSum1(int[] a){
int maxSum = 0;
for(int i = 0; i < a.length; i++){
int thisSum = 0;
for(int j = i; j < a.length; j++){
thisSum += a[j];
if(thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
}
```

Did you run it your slef with exactly your array - it returns 7

where do you see 7 in this array -

maximum subsequnce here will be just last element 6

and it should return 6

Why you don't answer to my question?

It is much easier to undesratnd once, then to

write all sorts of variants. If you understand it once

you'll not need to test all possible

variants.

counter example

At least this is defineitrl much less obvious way

If you are talking about better efficiency - as you told me you don't care - it is still not the best way

Explain tio me do you understand the original solution?

so it is also a way - but I prefer logically more claer solutions unless it comes to

efficiency - so the previos way was still better

in the wrong direction.

If you would have explained that, well - I understand how that one works and want to find

solution with two loops, rather than three - I would have thought about it in different way, and we would

have found common ground much faster.

Otherwise it is difficult to undersatnd, what is your goal and I was probably wasting time explaining to you something

which you understood before.

"The outer loop just iterates a.length times, the second loop iterates through an increasingly small subset of the array, and the inner loop performs the addition of array elements. Since the inner array only iterates once at a time, it is not necessary like the two outer loops. But the code inside of the inner loop is necessary."

That would have been the best answer! And I know my language may not be perfect, but now you know basically what I was looking for. I think you gave 36 comments for my question this time, but 1 or 2 would have been enough. I appreciate your help though as always.

Sorry if those were not so understandable to you - there are many words to choose and all people are different - which one to sleect it is not so easy.

As I know cannot guess which are the best words and they are different for different people - i try to use different wording hoping that one of it will strike the chord. In my experienxce when I read explanations on the web sites I much more often see that some details are not covered rather than

I am bothered with too many words on these sites.

Still if you understood the point, please let me know, that this is clear - I'd not write it so many times.

In general I'm more of a talker than writer - I do like to send many shorter mesages than one longer - as it creates more

impression of the talk than writing long texts.

By clicking you are agreeing to Experts Exchange's Terms of Use.

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

Java 1603 Error | 2 | 26 | |

mergeTwo challenge | 13 | 53 | |

Passing list of object to Oracle Database Procedure | 3 | 30 | |

create a gui in perl | 3 | 21 |

The viewer will learn how to implement Singleton Design Pattern in Java.

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

Connect with top rated Experts

**9** Experts available now in Live!