Maximum Contiguous Subsequence Sum and sequence

Question

I am trying to find to the max sum of an array and print the corresponding sequence that produces that max sum. I have been able to get the correct sum but when I try to print the sequence for some of the test arrays my program leaves off one of the indices. For example, for the array [1, -1, 2, 3, -2] my program finds the max sum of 5 but it only prints 1, -1, 2 instead of 1, -1, 2, 3. I know the problem is inside my for loop and my count variable not incrementing correctly but I do not know how to fix it.

    import java.util.*;

    public class practice
    {
        public static void main(String args[])
        {
            int arr[] = {1, -1, 2, 3, -2};
            int arr2[] = {1, 12, -2, -15, 10};
            int arr3[] = {0, -1, -3, -5, -6};
            int arr4[] = {1, 2, 3, 4, 5};
            int arr5[] = {1, 12, -2, 15, 10};

            subsequence(arr);
            subsequence(arr2);
            subsequence(arr3);
            subsequence(arr4);
            subsequence(arr5);

        }

        public static void subsequence(int[] arr)
        {
            int max = 0;
            int tempMax = 0;
            int count = 0;

            // My problem is in here:
            for (int i = 0; i < arr.length; i++)
            {
                tempMax += arr[i];
                if (max < tempMax)
                {
                    max = tempMax;
                    count++;
                }
            }

            System.out.println("count = " + count);
            System.out.println("Max sum is " + max);
            System.out.print("Sequence is: ");

            for (int j = 0; j < count; j++)
                System.out.print(arr[j] + " ");

            System.out.println("\n");
        }
    }

here is my output

    count = 3
    Max sum is 5
    Sequence is: 1 -1 2 

    count = 2
    Max sum is 13
    Sequence is: 1 12 

    count = 0
    Max sum is 0
    Sequence is: 

    count = 5
    Max sum is 15
    Sequence is: 1 2 3 4 5 

    count = 4
    Max sum is 36
    Sequence is: 1 12 -2 15

here is my edited code:

public class practice
{
    public static void main(String args[])
    {
        int arr[] = {1, -1, 2, 3, -2};
        int arr2[] = {1, 12, -2, -15, 10};
        int arr3[] = {0, -1, -3, -5, -6};
        int arr4[] = {-1, 2, 3, -4, -5};
        int arr5[] = {1, 12, -2, 15, 10};

        subsequence(arr);

        subsequence(arr2);

        subsequence(arr3);

        subsequence(arr4);

        subsequence(arr5);
    }

    public static void subsequence(int[] arr)
    {
        int max = 0;
        int tempMax = 0;
        int count = 0;
        int start = 0;
        int end = 0;

        if (arr[0] < 0)
           start++;


        for (int i = start; i < arr.length; i++)
        {
            tempMax += arr[i];

            if (max < tempMax)
            {
                max = tempMax;
                count = i;
            }

            if (Math.abs(arr[i]) < tempMax)
               end = i;


         }

         System.out.println("count = " + count);
         System.out.println("Max sum is " + max);
         System.out.print("Sequence is: ");

         if (arr[end] < 0)
               end--;

         for (int j = start; j <= end; j++)
             System.out.print(arr[j] + " ");

         System.out.println("\n");
         }

    }

and here is my new output:

count = 3
Max sum is 5
Sequence is: 1 -1 2 3 

count = 1
Max sum is 13
Sequence is: 1 12 

count = 0
Max sum is 0
Sequence is: 0 

count = 2
Max sum is 5
Sequence is: 2 3 

count = 4
Max sum is 36
Sequence is: 1 12 -2 15 10

you said this prints 1, -1, 2 instead of 1, -1, 2, 3 but what happened -2 here? — Kick Buttowski
– Kick Buttowski, Commented Jul 30, 2014 at 17:41
the reason -2 does not show up is because it does not create a max sum. if -2 was included it would make the sum equal to 3 when the actual max sum is 5. — shane
– shane, Commented Jul 30, 2014 at 17:51

Eran · Accepted Answer · 2014-07-30 17:36:59Z

1

Your count variable doesn't make sense, since you only increment it if you find a new candidate for the maximum. When you find a new maximum candidate, set count to the current index :

count = i;

Then when you print the sequence, change the condition to j <= count.

BTW, I'm not sure your implementation is correct. You always return a sub-sequence that starts in the beginning of the array. What if the sub-sequence with the max sum doesn't start at the beginning? (for example, in [-1,2,3,4,5], the max sequence is [2,3,4,5]).

answered Jul 30, 2014 at 17:36

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Kick Buttowski Over a year ago

what is max sequence here? what does it mean?

Eran Over a year ago

@KickButtowski The max sequence is the sub-array that produces the max sum.

shane Over a year ago

I did not consider that. any suggestions on how to go about that? Also i would like to just print 2, 3 instead of 1, -1, 2, 3

Kick Buttowski Over a year ago

what is the logic behind that?

Eran Over a year ago

@shane The naive way is to use a nested loop. The outer loop from 0 to array.length - 1. The inner loop from i to array.length - 1. The inner loop will find the max sum of a sequence starting in i. The outer loop would find the overall max sum.

|

Collectives™ on Stack Overflow

Maximum Contiguous Subsequence Sum and sequence

1 Answer 1

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related