[imu_1]

Hello everyone, I am having trouble understanding this method. I will appreciate your help.

public static int maxSubSum2(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; 
	} 

Lets say we have this array: 8,-4,3,2,-5,-6,10

So, on the first iteration, i=0; j=0; maxSum = 8, thisSum = 8.
2nd it: i=1 j=1; maxSum = 8, thisSum = 4
3rd it: i = 2; j = 2; maxSum = 8, thisSum =7
4th it: i=3,j=3, maxSum =9, thisSum = 9
5th it: i=4,j=4, maxSum =9, thiSum =4
6th it: i=5,j=5, maxSum =9 thisSum =-1
7th it: i=6, j=6, maxSum =9 thisSum = 8

Now, i ran this program nd the answer i got was 10, not 9. According to my understanding, I should be getting
9. We are finding maximum subsequence sum.

I will appreciate if you anyone will explain to me interms of iterations.

[macosxnerd101]

What this method does is start at the beginning of the array and add all the numbers, one at a time, to a sum variable. If at some point after an addition, if the sum > maxSum, update maxSum. After each iteration of the outer loop, the first nth element is ignored until you have no more elements to examine.

[jdwilliams51]

I think that 10 is correct. The last subsequence has only one value, the last element of the array which is 10.

[imu_1]

macosxnerd101, on 14 September 2011 - 07:23 PM, said:

After each iteration of the outer loop, the first nth element is ignored until you have no more elements to examine.

Macos, can you please explain more on this using the series of numbers i provided. In that way, i will understand exactly waht happends at each iteration. My problem is that I cant figure out how the inner loop runs starting from i at each iteration. So, if you will be kind enough to go thrugh it, not all iteration,atleast the first 3.

Thanks.

[macosxnerd101]

I added a System.out.println() in your code. It will show you exactly what is being added to thisSum, and the current value of thisSum on each iteration of the inner loop. That should help illustrate things more clearly.

public static int maxSubSum2(int [] a) 
   { 
      int maxSum = 0; 
	  
	  for(int i =0; i < a.length; i++) 
	  { 
	     int thisSum = 0; 
		 
		   for(int j=i; j < a.length; j++) 
		   { 
                      System.out.println("Adding " + a[j] + " to " + thisSum);
		      thisSum += a[j]; 
			  
			  if(thisSum > maxSum) 
			    maxSum = thisSum; 
		   } 
	  }
	  
	  return maxSum; 
	} 

[elgose]

macosxnerd101, on 14 September 2011 - 09:23 PM, said:

I added a System.out.println() in your code. It will show you exactly what is being added to thisSum, and the current value of thisSum on each iteration of the inner loop. That should help illustrate things more clearly.

This.

I'm not sure how you're adding it, but the way your code works, your thisSum will be:
1st: Sum of: 8,-4,3,2,-5,-6,10
2nd: Sum of: -4,3,2,-5,-6,10
3rd: Sum of: 3,2,-5,-6,10
4th: Sum of: 2,-5,-6,10
...
7th: Sum of 10

From this, you'll find that after each iteration of i:
1st: i=0;j=0; maxSum=9; thisSum=8;
2nd: i=1;j=1; maxSum=9; thisSum=0;
3rd: i=2;j=2; maxSum=9; thisSum=4;
4th: i=3;j=3; maxSum=9; thisSum=1;
5th: i=4;j=4; maxSum=9; thisSum=-1;
6th: i=5;j=5; maxSum=9; thisSum=4;
7th: i=6;j=6; maxSum=10; thisSum=10;

So your final answer is 10.

macosxnerd101 offers a wonderful tip here. Not sure how it's going down? System.out.println(...) is practically free, so throw some in there at key places to try and figure out what's going on. This will be an invaluable debugging skill later on.

[jdwilliams51]

jdwilliams51, on 14 September 2011 - 07:39 PM, said:

I think that 10 is correct. The last subsequence has only one value, the last element of the array which is 10.

I put prints before and after the logic to update maxSum. Here's the code change, the results follow:

   public static int maxSubSum2(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];
                System.out.printf(
                        "i j thisSum old maxsum: %d %d %d %d", i, j, thisSum, maxSum);
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
                System.out.printf("...new maxsum: %d\n", maxSum);
            }
        }
        return maxSum;
    }

Results:
i j thisSum old maxsum: 0 0 8 0...new maxsum: 8
i j thisSum old maxsum: 0 1 4 8...new maxsum: 8
i j thisSum old maxsum: 0 2 7 8...new maxsum: 8
i j thisSum old maxsum: 0 3 9 8...new maxsum: 9
i j thisSum old maxsum: 0 4 4 9...new maxsum: 9
i j thisSum old maxsum: 0 5 -2 9...new maxsum: 9
i j thisSum old maxsum: 0 6 8 9...new maxsum: 9
i j thisSum old maxsum: 1 1 -4 9...new maxsum: 9
i j thisSum old maxsum: 1 2 -1 9...new maxsum: 9
i j thisSum old maxsum: 1 3 1 9...new maxsum: 9
i j thisSum old maxsum: 1 4 -4 9...new maxsum: 9
i j thisSum old maxsum: 1 5 -10 9...new maxsum: 9
i j thisSum old maxsum: 1 6 0 9...new maxsum: 9
i j thisSum old maxsum: 2 2 3 9...new maxsum: 9
i j thisSum old maxsum: 2 3 5 9...new maxsum: 9
i j thisSum old maxsum: 2 4 0 9...new maxsum: 9
i j thisSum old maxsum: 2 5 -6 9...new maxsum: 9
i j thisSum old maxsum: 2 6 4 9...new maxsum: 9
i j thisSum old maxsum: 3 3 2 9...new maxsum: 9
i j thisSum old maxsum: 3 4 -3 9...new maxsum: 9
i j thisSum old maxsum: 3 5 -9 9...new maxsum: 9
i j thisSum old maxsum: 3 6 1 9...new maxsum: 9
i j thisSum old maxsum: 4 4 -5 9...new maxsum: 9
i j thisSum old maxsum: 4 5 -11 9...new maxsum: 9
i j thisSum old maxsum: 4 6 -1 9...new maxsum: 9
i j thisSum old maxsum: 5 5 -6 9...new maxsum: 9
i j thisSum old maxsum: 5 6 4 9...new maxsum: 9
i j thisSum old maxsum: 6 6 10 9...new maxsum: 10
max subsum: 10

That last line was printed by main(..).