Find the subarray with the max sum 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&lt;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&lt;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&lt;array.length;i++){*/
            for(int i=0;i&lt;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 &lt;= i; j++) {
                    currentArray[j] = array[j];

                    psuedoIndex=psuedoIndex+1;
                }
            }
            else {
                currentArray = new int[i+1];
                for (int j = 0; j &lt;= 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))&gt;largestSum){
                previousLargestSum=largestSum;
                largestSum=sum;
                for(int k=0;k&lt;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&lt;currentArr.length;index++){
            sumOfElements +=currentArr[index];

        }
        //System.out.println("sum is:" + sumOfElements);
        return sumOfElements;
    }    
}
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 &lt;= i; j++) {


vs.

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


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



if((sum = calculate(currentArray))&gt;largestSum){


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

int sum = calculate(currentArray);
if (sum &gt; largestSum) {




private int calculate(int [] currentArr){



Non-optimal spacing in both the method declaration and method body.
Unclear method name. calculate what exactly? Rename it to calculateSum, please.
Perfect use-case for a for-each loop.
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&lt;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)