Solved

# What is this maximum subsequence sum program trying to do?

Posted on 2011-10-02
Medium Priority
553 Views
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;
}
}
``````
0
Question by:shampouya
• 37
• 13

LVL 47

Expert Comment

ID: 36900419
I think they calculate sume of all subsequences and determine which is maximum -0 if you havenegative numbers in the array that would make sense
0

Author Comment

ID: 36900427
what is a subsequence?
0

LVL 47

Expert Comment

ID: 36900430
In general subsequence is any subset of the array
0

LVL 47

Expert Comment

ID: 36900434
I don't think there is strict definition - should the elements be taken in the same order in the subsequnce always - proabably they should
0

LVL 47

Expert Comment

ID: 36900435
In this example they also take that they should be consecutive elements of the array
0

LVL 47

Expert Comment

ID: 36900441

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
0

LVL 47

Expert Comment

ID: 36900445
You can esily check that

1+3-6+3+9
1+3
1+3-6
3-6+3
etc

they all give smaller sum
0

LVL 47

Expert Comment

ID: 36900447
of course if all numbers in the array are positive then it will be just the sum of all elements
0

LVL 47

Expert Comment

ID: 36900456
So you see they check all combinations of i and j between 0 and last index and
calculate sum of all numbers between and then detrmine the maximum of the sum
0

Author Comment

ID: 36900458
Ok, so it's better for arrays with negative numbers. But why are there three for loops?
0

LVL 47

Expert Comment

ID: 36900462
This is by the way not the optimal way of doing it, they could save on the number of additions but for
not too big arraays it is not important
0

LVL 47

Expert Comment

ID: 36900463
see my explanation couple of points above why there are three loops
0

LVL 47

Expert Comment

ID: 36900467
first two loops establish border indexes and the third one does the summation
0

LVL 47

Expert Comment

ID: 36900474
actually I was not right when I was saying that they could have done it more effectively - at least the way they do it - it is reasonable
0

LVL 47

Expert Comment

ID: 36900508
If they just need to get the maximum sum - it would be more effective first to summ all consecutive positive elmnets and all consecutive negative and replace the all consecutive groups of positive elemets and negative elements
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
0

Author Comment

ID: 36900523
I'm not focused on how to make the program better or more efficient, I'm just trying be able to read the code. I feel like a kindergardener trying to read War and Peace.

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?
0

LVL 47

Expert Comment

ID: 36900545
Just think that each of subsequences is defuined by two indexes - the start index and the begiining index
0

LVL 47

Expert Comment

ID: 36900551
So, how would you select two indexes indepoendnetly from all of the indexs present in your array?
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
0

LVL 47

Expert Comment

ID: 36900555
After you slected the starying index and the ending index - then your third loop will be going through all elements
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
0

LVL 47

Expert Comment

ID: 36900568
This seeem to be quite logical to me; let me know if something is unclear; proabbly the main point is to understand that each subsequence is
determined by two index values - the starting index and the ending index - and to select two indexs you need to have two loops
0

Author Comment

ID: 36900731
Here's how you can explain it me: Let's say in this program myArray is {1,2,3,4,-5}. To me, the first loop of the program loops five times and goes through these operations in the inner loops:

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

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

LVL 47

Expert Comment

ID: 36900840
No, this is not how it happens

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

0

LVL 47

Expert Comment

ID: 36900850
Please try to understand this important point:

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

0

LVL 47

Expert Comment

ID: 36900852
Please, read my last post and try to pinpoint which of the statements you do not undersatnd - I'll explain it once again

0

Author Comment

ID: 36900921
I think you misunderstood my last post.

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.

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

Return 5

0

LVL 47

Expert Comment

ID: 36900924

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

0

LVL 47

Expert Comment

ID: 36900926
there is no assumption that subsequece with always be the tail of the sequence - like in your cases
0

LVL 47

Expert Comment

ID: 36900928
In your caculations you do not vary the ending index of the subsequernce - it is always equal to 4 (the last index of the array).
0

LVL 47

Expert Comment

ID: 36900933
there is no assumption that the last index of the subsequence should coincide with the last index of the array,
that's why you need to gro through allpossible pairs of starting and ending indexes to go through all possible subsequences
0

Author Comment

ID: 36900935
Ok so can you type every single calculation that the computer does, line by line, even the ones that it discards?
0

LVL 47

Expert Comment

ID: 36900940
let's limit to 4 elements:
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
0

Author Comment

ID: 36900954
I'm assuming the commas you wrote mean addition, like this?

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

0

LVL 47

Expert Comment

ID: 36900956
I forgot the last case (just the last element):

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

0

LVL 47

Expert Comment

ID: 36900960
I wrote out subsequences.
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
0

Author Comment

ID: 36901026
Could the method have just been written like this? It seems so much simpler:
``````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;
}
``````
0

LVL 47

Expert Comment

ID: 36901077
No, this for the starters will sum up one element many times
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

ID:36900850
and explain what poinnt you don't understand.

0

Author Comment

ID: 36901088
I think you're wrong, I just tried out this code, which only has two loops, and it works.

``````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;
}
}
``````
0

LVL 47

Expert Comment

ID: 36901146
Check with this array:
(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
``````
0

Author Comment

ID: 36901178
Sorry I meant to write this code. This seems to work:
``````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;
}
}
``````
0

LVL 47

Expert Comment

ID: 36901205

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.

0

LVL 47

Expert Comment

ID: 36901220
No I was wrong 7 is correct for your array
but the code is wring
0

LVL 47

Expert Comment

ID: 36901222
The code is wriond becuase you do not cover those sequences which do not conatin last element
0

Author Comment

ID: 36901225
7 is correct though isn't it?
0

LVL 47

Accepted Solution

for_yan earned 2000 total points
ID: 36901227
for your array 7 is correct
0

Author Closing Comment

ID: 36901240
thanks
0

LVL 47

Expert Comment

ID: 36901242
Maybe you are right - it is a possiblity - but you are not checking those which does not contain last eleemnt, I just can't come up with
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?

0

LVL 47

Expert Comment

ID: 36901247
yes, you are going through them in the process - before you reach the last elemnt -
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
0

LVL 47

Expert Comment

ID: 36901276
In general, when I ask you direct questions - please answer, because it creates misunderstanding and drives my thought
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.
0

Author Comment

ID: 36901357

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

LVL 47

Expert Comment

ID: 36901415
well, I agree that maybe my wording was not the best - but unfortunatelt I not alwys can guess what particular words you'll consider most clear - I used some other words which seem more inforamtive for me.
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.

0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing instaâ€¦
Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a clâ€¦
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Downâ€¦
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
###### Suggested Courses
Course of the Month15 days, 1 hour left to enroll