Find the subarray with the max sum

Question

In an interview I was asked to solve the following problem:

find a subarray with max sum

I have written a piece of code for the same. I need your help in reviewing this code.

package com.ankit.rnd;

public class MaxSubArrSum {

    int largestSum=0;
    int previousLargestSum=0;

    public static void main(String[] args) {
        // int [] array = {-2,1,-3,4,-1,2,1,-5,4};
        int [] array = {-5,1,-3,7,-1,2,1,-4,6};
        // int [] array = {-2,-3,-4,2};

        MaxSubArrSum obj = new MaxSubArrSum();

        for(int varindex=0;varindex<array.length;varindex++){

            // int sumis =new MaxSubArrSum().findSum(varindex,array);
            // System.out.println("sumis::" +sumis);
            obj.splitCurrentArray(varindex,array);
        }
    }


    private void splitCurrentArray(int in, int[] arr) {

        int [] tempArr = new int[arr.length-in];
        for(int i=in;i<arr.length;i++){
            if(in ==0){
                tempArr[i] = arr[i];
            }
            else{
                tempArr[i-in] = arr[i];
            }
        }

        int sum =findSum(in, tempArr);
        System.out.println("Previous Largest Sum::" + previousLargestSum);
        System.out.println("Largest Sum found:" + sum); 
    }  

    @SuppressWarnings("unused")
    private int findSum(int start,int [] array) {


        int[] currentArray ={};


        int [] largestArray = new int[array.length];
        int sum=0;
        /*for(int i=start;i<array.length;i++){*/
            for(int i=0;i<array.length;i++){
            //a little inefficient here as it always create an array with size more than total number of elements that should be there in the temp array.
            int psuedoIndex=i;
            if(start==0){
                currentArray = new int[i + 1];
                for (int j = 0; j <= i; j++) {
                    currentArray[j] = array[j];

                    psuedoIndex=psuedoIndex+1;
                }
            }
            else {
                currentArray = new int[i+1];
                for (int j = 0; j <= i; j++) {
                    currentArray[j] = array[j];

                    /*
                     * if(psuedoIndex == array.length){ //needs a fix. as we
                     * have reached the end of the array. //currentArray[j] =
                     * array[psuedoIndex-1]; currentArray[j] = 0; break; } else{
                     * 
                     * currentArray[j] = array[psuedoIndex]; is commented out
                     * because it missed the element in the previous array.
                     * 
                     * 
                     * //currentArray[j] = array[psuedoIndex]; currentArray[j] =
                     * array[j]; }
                     */

                    psuedoIndex=psuedoIndex+1;
                }
            }


            if((sum = calculate(currentArray))>largestSum){
                previousLargestSum=largestSum;
                largestSum=sum;
                for(int k=0;k<currentArray.length;k++){
                    System.out.print(currentArray[k] + "|");

                }
                System.out.println("");
            }
        }
        return largestSum;
    }

    private int calculate(int [] currentArr){
        int sumOfElements =0;
        for(int index=0;index<currentArr.length;index++){
            sumOfElements +=currentArr[index];

        }
        //System.out.println("sum is:" + sumOfElements);
        return sumOfElements;
    }    
}

Answer 1

Reading and debugging your code and two other answers pops up. (And a third one popped up while writing this answer)

There's a whole lot to say about your code. I will provide comments about your existing code and also comment about a different way to think about the problem.

---

You have a whole lot of commented code, and you don't write why it has been commented. Either way, I would recommend removing all your commented code before putting it up for review.

The //needs a fix comments here almost made me close the question for not being working code. Your code works (even though it is inefficient) so remove all such commented code:

                /*
                 * if(psuedoIndex == array.length){ //needs a fix. as we
                 * have reached the end of the array. //currentArray[j] =
                 * array[psuedoIndex-1]; currentArray[j] = 0; break; } else{

---

        if(in ==0){
            tempArr[i] = arr[i];
        }
        else{
            tempArr[i-in] = arr[i];
        }

There is no need to treat in ==0 as a special case here. Your else can take care of that as well. Replace all this with:

tempArr[i-in] = arr[i];

---

            currentArray = new int[i + 1];
            currentArray = new int[i+1];

Please use consistent spacing. And this applies to all your code. I recommend using spaces around + signs and such.

Compare

for (int j = 0; j <= i; j++) {

vs.

for(int i=0;i<array.length;i++){

I prefer the first version. No need to make code too compact. Itwillonlymakeithardertoread (right?).

---

if((sum = calculate(currentArray))>largestSum){

Sure, this works, but I think it would be more readable by splitting it on two lines.

int sum = calculate(currentArray);
if (sum > largestSum) {

---

private int calculate(int [] currentArr){

1. Non-optimal spacing in both the method declaration and method body.
2. Unclear method name. calculate what exactly? Rename it to calculateSum, please.
3. Perfect use-case for a for-each loop.

4. Here's what I would do:

   private int calculate(int[] currentArr) {
       int sumOfElements = 0;
       for (int value : currentArr) {
           sumOfElements += value;
       }
       return sumOfElements;
   }
   

---

for(int k=0;k<currentArray.length;k++){
    System.out.print(currentArray[k] + "|");
}

There is a Arrays.toString method, use it.

System.out.print(Arrays.toString(currentArray));

---

A different approach

You're using way too many for-loops for my taste.

Consider your starting array:

int[] array = {-5,1,-3,7,-1,2,1,-4,6};

It starts with a negative number, and as you want to find the sub-array with the largest sum, there's no need to start counting on a negative number.

So, skipping that one we have these left:

int[] array = {1,-3,7,-1,2,1,-4,6};

By starting on \$1\$ and looping until you encounter a negative number, you can see that \$1 + -3 = -2\$, which makes this part unnecessary to check. It will not improve your array. The highest sum we can create out of this is simply \$1\$ for now.

Skipping the \$1\$ and \$-3\$ and we end up with:

int[] array = {7,-1,2,1,-4,6};

Now let's start looping. \$7 + -1 = 6\$ so that's good, let's continue.

\$2 + 1 + -4 = -1\$ OK, that ended up being a not so pleasant experience, but considering the \$6\$ we have from before, we end up with \$5\$ so let's continue.

\$6\$ now that's good. And now the array has ended. Adding this to our previous result and we end up with \$5 + 6 = 11\$ and we have our final result.

There's no need to start the original looping at 2 which will only count 2,1,-4,6 as the 7,-1 in the beginning of the array will give a more positive result than starting from this 2.

By taking this in consideration, you can increase the speed of your algorithm a lot.

The code for this approach can be found and review in my Code Review question

---

Edit: Another addition. You don't provide a method to retrieve the result without printing it. Your way of returning the result seems to be to simply print it to the console. That's not a good way. You should have provided a method like this: int[] maxSubArraySum(int[] array)

Answer 2

Part-way through an answer, and another answer pops up.

My answer is slightly different to Prizoff's, so I'll keep it.

In an interview, the trick is to take a moment to think about the problem, and what the requirements are. In this case, it feels like you have taken the wrong path to getting the results. The simplest solution is to keep a running tally in two loops

int maxsum = Integer.MIN_VALUE;
int maxl = -1;
int maxr = -1;
for (int left = 0; left < array.length; left++) {
    int sum = 0;
    for (int right = left; right < array.length; right++) {
        sum += array[right];
        if (sum > maxsum) {
            maxsum = sum;
            maxl = left;
            maxr = right;
        }
    }
}

// if return just sum....
return maxsum;

// if return array:
return Arrays.copyOfRange(array, maxl, maxr + 1);

Answer 3

It's hard to say but if I get this with an interview, you will not pass.
On the other hand, I'll find it good you come to here to learn.

Number 1 is really red flags.

Let's start with the review.

1. No public static void main(String args) with logic.

I removed the comment lines to point it out.

public static void main(String[] args) {
    int [] array = {-5,1,-3,7,-1,2,1,-4,6};

    MaxSubArrSum obj = new MaxSubArrSum();

    for(int varindex=0;varindex<array.length;varindex++){
        obj.splitCurrentArray(varindex,array);
    }

}

The public static void main(String[] args) is for a testing purpose and to show your code works.
A JUnit should be better but oke I can live with that for an test.
You init the object like this : MaxSubArrSum obj = new MaxSubArrSum();.
This is actually a good start, but then you go so off.
You need to implement a for.
The class should return you an array with the maximum sum, and this you could print out in the main.

2.Sum of int's is should never be an int.

When you are counting int's together you have to take care with the max and min value of int.
If your array has 2 values but both max int value, you will have an overflow.
So it's better if you declare sum as long.

3.Scoping variables

int largestSum=0;
int previousLargestSum=0;

Are now package private. Declare them private and if you need them outside provide getters and/or setters.

So it should be :

private int largestSum = 0;
private int previousLargestSum = 0;

public int getLargestSum() {
    return largestSum;
}

4.Default values

A global variable has a default value.
For int is this 0.
For Integer is this null.

int largestSum = 0;
int previousLargestSum = 0;

should be :

private int largestSum;
private int previousLargestSum;

5.Variable naming

Overall you do it correct, but sometimes it's off :

private void splitCurrentArray(int in, int[] arr) {

The in can be more clear like this :

private void splitCurrentArray(int startIndex, int[] arr) {

6.Remove commentlines with code.

When you have to give code for an interview, do not let commented code standing.

7.Java Doc

Write java doc for each public method.

8.Mine solution

I have created 2 classes, where one is just a data class.
This will show that you are aware of OO programming and you can use it.

package com.ankit.rnd;

/**
 * This class hold the values of a subArray of a given array.
 * We store the beginIndex, endIndex and the total sum from beginIndex to endIndex.
 * We can only init with some data, no setters are foreseen cause changing one data affects other data to.
 */
public class SubArrayDetails {

    private int beginIndex;
    private int endIndex;
    private long totalSum;

    /**
     * The only constructor for this class.
     * 
     * @param beginIndex the beginIndex of the subArray.
     * @param endIndex the endIndex of the subArray.
     * @param totalSum the total sum of all objects from beginIndex to endIndex.
     */
    public SubArrayDetails(int beginIndex, int endIndex, long totalSum) {
        this.beginIndex = beginIndex;
        this.endIndex = endIndex;
        this.totalSum = totalSum;
    }

    /**
     * Returns the beginIndex.
     * @return int beginIndex
     */
    public int getBeginIndex() {
        return beginIndex;
    }

    /**
     * Returns the endIndex.
     * @return int endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * Returns the totalSum.
     * @return long totalSum
     */
    public long getTotalSum() {
        return totalSum;
    }
}

The next class is the calculations itself.
Because the UC is so little it stands open for interpretation like what do I have to do with all negatifs?
In mine solution, an array of all negatifs shall work and spit out an array with 1 number. There is also no details to do when more subArrays are found with the same highest sum so I just return 1 of them.

package com.ankit.rnd;

/**
 * This class will find and return the subarray where the highest sum is found.
 * Cause this operation is a helper operation we made all the methods static.
 * The class is final so no extension of class is possible. The class has
 * private constructor to forbid initialisation of this class.
 *
 */
public final class MaxSubArrSum {

    public static void main(String[] args) {
//       int [] array = {-2,1,-3,4,-1,2,1,-5,4};
        int[] array = {-5, 1, -3, 7, -1, 2, 1, -1, 5, -4, 6};
//        int [] array = {-5,-3,-4,-8};

        int[] maxSumArray = MaxSubArrSum.getMaxSumArray(array);
        System.out.println("Maximum array has size of " + maxSumArray.length);
        for (int number : maxSumArray) {
            System.out.print(String.valueOf(number) + " ");
        }
    }

    private MaxSubArrSum() {
    }

    /**
     *
     * @param startArray
     *
     * @throws AssertionError when array is null or array.lenght is 0.
     *
     * @return first sub with the highest sum
     */
    public static int[] getMaxSumArray(int[] startArray) {
        if (startArray == null || startArray.length == 0) {
            throw new AssertionError("Precondition failed, null object or zero size array.");
        }
        if (startArray.length == 1) {
            return startArray;
        }
        return findMaxSumArray(startArray);
    }

    private static int[] findMaxSumArray(final int[] startArray) {
        SubArrayDetails highestSumSubArrayDetails = new SubArrayDetails(0, 0, startArray[0]);
        for (int counter = 0; counter < startArray.length; counter++) {
            highestSumSubArrayDetails = findHighestSubArray(startArray, counter, highestSumSubArrayDetails);
        }
        int[] resultArray = new int[highestSumSubArrayDetails.getEndIndex() - highestSumSubArrayDetails.getBeginIndex() + 1];
        System.arraycopy(startArray, highestSumSubArrayDetails.getBeginIndex(), resultArray, 0, resultArray.length);
        return resultArray;
    }

    private static SubArrayDetails findHighestSubArray(final int[] array, final int indexLowestBound, final SubArrayDetails highestSumSubArrayDetailsKnown) {
        long tempSum = 0;
        SubArrayDetails highestSumSubArrayDetails = highestSumSubArrayDetailsKnown;
        for (int counter = indexLowestBound; counter < array.length; counter++) {
            tempSum += array[counter];
            if (highestSumSubArrayDetailsKnown.getTotalSum() < tempSum) {
                highestSumSubArrayDetails = new SubArrayDetails(indexLowestBound, counter, tempSum);
            }
        }
        return highestSumSubArrayDetails;
    }
}

Answer 4

It can be done a lot more simpler. What reason do you split array for? I think, you should change global approach. It is a very simple task for 2 nested loops:

You should use something like this in pseudocode:

for (int i = 0; i < array.length; ++i) {
    for (int j = i; j < array.length; ++j) {
        getSubArraySum(i,j);

        // ...
        // Here should be a code for comparing subArray sum with maximum value
        // and storing i and j for this maximum sum
    }
}

Then implement getSubArraySum() - it is very easy method with one for-loop (or for-each for better readability) and finish the task. No need for any OOP and classes in this particular case, in my opinion.