Suppose that you have an array of both positive and negative integers. Write a function that will find the continuous sequence within the array that has the largest sum of numbers. Return the sum.

For example, suppose that you are given the following array:

{4, -1, 2, -2, -1, -3}.

Then the output of the function should be “5”, because of the fact that the sequence of {4, -1, 2}, when 4 + -1 + 2 is calculated it will return 5. That is the highest sum of any continuous values within the array.




Be sure to really understand what is being asked in this problem. First off – what is meant by continuous values? Well, it means values that appear right after one another within the array – so we can’t just sum 4 and 2 from the array (to get 6), because those values don’t appear in continuous order. For this reason, this interview question is also known as the maximum subarray problem, because we are essentially trying to find the array within the larger array that has the largest sum of values. But also note that the largest “subarray” could be the entire array if all of the values summed together give the largest sum.

Also, note that the problem just asks us to return the largest sum – it does not ask us to return the actual sequence which is responsible for generating the sum. This means that we don’t have to keep track of the sequence itself, but just the actual sum itself – and this actually simplifies the problem.

What if the array only one value in the array is the highest value?

Suppose we have an array like {4, -5, 6} – then could “6” be considered the highest continuous sequence. We will assume that yes it can be – although you may want to clarify with your interviewer if asked this question in an interview scenario. He/she may not consider just one value in the array to be a sufficient answer, in which case the answer above would be 4 + -5 + 6, which is 5. But, be sure to clarify what your interviewer wants since that shows attention to detail – which is a quality every employer desires.

What if the array only has negative numbers?

Well, there are a couple of possibilities – you could return the highest number, which will of course be negative. Or you could just return “0” to indicate that the “empty sub-array” is highest – this is what we will assume in our solution. Again, clarify with your interviewer if you are in that situation.

Solution to finding the continuous sequence with largest sum




Now that we have a better understanding of the problem, let’s come up with a solution. It’s clear that we will have to iterate through the entire array to find the largest continuous sequence. But how should we come up with an algorithm to solve this problem? Well, we will clearly need one variable to hold the highest sum. And, we will need another variable to hold the “current” sum, so that we can compare this value to the current value being stored in the maximum variable. If the current sum is higher then we set the maximum variable equal to the current sum. And if the current sum is less than 0 then we reset the current sum variable to 0, because of the fact that we will not allow negative values to be returned as the maximum.

With that in mind, we can come up with the following Java code as our solution, and we are done:

public static int findMaxSum(int[ ] anArray)
{
  int currentSum = 0;
  int currentMax = 0;

  for (int j=0; j < anArray.length; j++)
  {
    currentSum += anArray[ j ];

   if (currentMax < currentSum) 
     currentMax = currentSum;
   else if (currentSum < 0)
     currentSum = 0;
  }
 
  return currentMax;
     
}


Hiring? Job Hunting? Post a JOB or your RESUME on our JOB BOARD >>

Subscribe to our newsletter for more free interview questions.

  • Uba Chan

    Its not the correct solution .
    try this input [21,2,-3,7,4,1]