Getting the continues sequence with the biggest sum in the given sequence

Gone through a problem in which we had to find the sequence with the largest sum in a given sequence. To elaborate the question, a sequence is given with positive and negative integers mixed say, {3, -4, 5,-2, 10}. In this, continues sequence with the largest sum is {5, -2, 10}. Tried the below solution with the time complexity of O[N].

* Class to find the continuous sequence with the largest sum in a given sequence.
public class MaxSumSequence
public static void main(String[] args)
// The sequence in which we need to find the (sub-)seuence with the
// largest sum.
int[] a={6,-6,1,11};
Sequence aMaxSequence = getMaxSumSequence(a);
System.out.print("The continuos sequence with the maximum sum:{");
for(int i=aMaxSequence.start;i<aMaxSequence.end;i++)

private static Sequence getMaxSumSequence(int[] a)
Sequence theMaxSequence = new Sequence(0, 0, a[0]);
Sequence theCurrentSequence = new Sequence(0, -1, 0);
for(int i=0;i<a.length;i++) { theCurrentSequence.end = i; theCurrentSequence.sum+=a[i]; if (theCurrentSequence.sum > theMaxSequence.sum)
theMaxSequence.start = theCurrentSequence.start;
theMaxSequence.end = theCurrentSequence.end;
theMaxSequence.sum = theCurrentSequence.sum;
// If the current sequence is not have a sum greater than 0, its not
// going to contribute for the sequence
return theMaxSequence;

* The class represent a sequence.
private static class Sequence
public Sequence(int theStart,int theEnd,int theSum)
start =theStart;
end = theEnd;
sum = theSum;
int start;
int end;
int sum;


Author: kannan_r

Just one among million. Software Engineer by profession. A bit interested in Math and Computing. Sometimes feeling that my interests are worth to be recorded and shared. This is just an initiative for my sharing;-)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s