What is this maximum subsequence sum program trying to do?

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

what is a subsequence?

In general subsequence is any subset of the array

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

In this example they also take that they should be consecutive elements of the array

in you use this array:

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

Select allOpen in new window

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

You can esily check that

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

they all give smaller sum

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

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

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

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

see my explanation couple of points above why there are three loops

first two loops establish border indexes and the third one does the summation

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

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

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?

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

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

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

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

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?

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

Select allOpen in new window

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

Please, read my post
ID:36900850
and explain what poinnt you don't understand.
 

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

Select allOpen in new window

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

Select allOpen in new window

Output:

7

Select allOpen in new window

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

Select allOpen in new window

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.

No I was wrong 7 is correct for your array
but the code is wring

The code is wriond becuase you do not cover those sequences which do not conatin last element

7 is correct though isn't it?

thanks

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?

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

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.

I can't respond to everything you say, because you provide so much information, most of which I'm not asking for. For example, in several of your posts you talk about efficiency, and optimal solutions, even though those were not part of my question. It's hard to follow your answers when you provide information that's not directly related to my question, and when you provide 5 responses for every question that I ask. I appreciate your knowledge and help but sometimes your answers are far too long. When I asked the question, why are there three loops, for example, you could have just said:

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

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.