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;


Number divisible by 2,4,8,16../5,25,125..

For any number 2^n(or 5^n), if you need to find out if it is a factor of number X, it is enough if you check the last n digits of the number X.

For ex., say a number 120016, if I need to find if the number is divisible by 16(=2^4), I just need to check if the last 4 digits is divisible by 4. So here 120016 is divisible by 16, because the last 4 digit is divisible by 16.

Now, let’s not convinced just with some shortcut.

Let’s understand the concept by taking a 5 digit number represented by  abcde, where a,b,c,d,e each represents some decimal from 0 to 9.

I need to find out if the number abcde is divisible by 8(=2^3).

Expressing the number abcde as ab000 +cde

So now, ab000 is nothing but abX1000, no doubt this is divisible by 8.

Now we just need to confirm if the number cde is divisible by 8. That’s it for any number X , to confirm if it is divisible by 2^n we just need to check if the last n digits is divisible by n.

The similar way we can prove for powers of 5..

2^n = (1+2+4+…2^(n-1))+1

This is one thing that I noticed. Then tried proving it, the below is the proof.

There is a proof that we can get it through binary(To be frank, I got this proof from my friend;), the way that I tried is simple, I just added the 1’s and kept taking out the 2’s).
Take the RHS and express it in binary,
The binary of

1 is 1,
2 is 10
4 is 100

And 2^n-1 is 100..(n-1)0’s
So when I express the sum 1+2+4+…2^(n-1) as binary,
I’ll get 1111…(n-1 1’s)

Now consider the RHS,
1111….(n-1 1’s)+1

So adding 1 at the last will keeps giving a 1 carried to its preceding position.
And at last you’ll get 100..(n 0’s)

Which when expressed in decimal is 2^n
That’s it..:-)

X*(X+1)*100+25 – a perfect square

Once gone through a shortcut to find square of a number that ends with 5.

For any number that is of format X5 i.e, 10X+5. The square will be X*(X+1)*100+25.

To say it with example, say a number 45,which is 4*10+5. Hence here the X is 4. So the square will be




The process that we do above might seem tedious at first glance. But not. You just write X*(X+1) then 25 next to that. At the place of ones and tens you are getting 0 anyhow and adding 25 is same as appending 25 to X*(X+1).

Just tried to write the proof for the above.

So, we wanted to square the number 10X+5. So see how the equation evolves to get the another form.




= x(x+1)*100+25

So whatever we see in the format x(x+1)*100+25, is a perfect square with the square root as 10x+5.

Hence 9025 is a perfect square with root as 95.

13225 is a perfect square with root as 115.

38025 is a perfect square with root as 195.

We just have to see if the number, after stripping off the 25, is of format x*(x+1).